unordered Tuples
I saw your problem as a partition problem, so I tried the following function:
unorderedTuples[len_] := Flatten[IntegerPartitions[#, {len}, Range[9]] & /@ Range[len, 9*len], 1]
In short, it looks for all the ways you can sum the numbers 1-9 from len to 9*len for a len-tuple.
There's some ordering difference between your method and this function, but
Sort@(Sort /@ unorderedTuples[3]) == Nest[f, Table[{i}, {i, Range[9]}], 2]
(* True *)
Sort@(Sort /@ unorderedTuples[10]) == Nest[f, Table[{i}, {i, Range[9]}], 9]
(* True *)
Lastly, timing:
unorderedTuples[10] // AbsoluteTiming
(* 0.0227264 *)
Nest[f, Table[{i}, {i, Range[9]}], 9] // AbsoluteTiming
(* 0.273851 *)
This solution is not as good and not as fast as the one by @Dubs, but perhaps it is of some interest.
Your example could be written as
Flatten[Table[{i, j, k}, {i, 1, 9}, {j, i, 9}, {k, j, 9}], 2]
We can generalize this to larger tuples of size n
as follows:
n = 10;
result = With[
{list = Table[Unique[it], {n}]},
{iter = Sequence @@ Table[{list[[i]], If[i == 1, 1, list[[i - 1]]], 9}, {i, n}]},
Flatten[Table[list, iter], n - 1]
];
For n=20
, it takes 5.6 s on my machine vs 1.2 s using the method by @Dubs.
As ciao astutely remembered the heart of this method has been posted earlier by someone else.
- Repeatedly take n elements from a list
Despite being impressed by that answer at the time I lost all conscious memory of it.
My variation of it below is useful (faster) in the case of this particular question.
I took a look at this a few hours later and I realized the solution was staring me in the face.
This is now competitive with Dubs' IntegerPartitions
solution, especially if you consider that unlike his it produces a fully sorted list by default.
f2[n_, m_] :=
Subsets[Range[m + n - 1], {n}] //
Subtract[#, ConstantArray[Range[0, n - 1], Length @ #]] &
Test:
f2[5, 9] === Sort[Sort /@ unorderedTuples[5]]
True
If one includes sorting my code is significantly faster than unorderedTuples
; if one does not is it still not too shabby. Closer still after the last update.
Sort[Sort /@ unorderedTuples[20]] // Length // RepeatedTiming
unorderedTuples[20] // Length // RepeatedTiming
f2[20, 9] // Length // RepeatedTiming
{4.643, 3108105} {1.15, 3108105} {1.35, 3108105}