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}