Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. It only takes a minute to sign up.
Sign up to join this community
I want to get all the non-descending tuples of a list with given length, for example:
f[{1,2,3,4},{3}]
{{1,1,1},{1,1,2},{1,1,3},{1,1,4},{1,2,2},{1,2,3},{1,2,4},{1,3,3},{1,3,4},{1,4,4}, {2,2,2},……,{4,4,4}}
A function lies between Tuples and Subsets to some degree.
Is the an efficient way to achieve this? (It should be general for all kind of elements, like Tuples, not specifically for Integers.)
A general solution for your problem should not create all tuples, only to throw most of them away. Additionally, one should consider the situation when the elements in the list cannot be compared, but the user knows that they are ordered. Therefore, here is an approach which creates the positions rather the elements itself.
When we create all tuples and highlight the elements for your specific example, we notice a pattern:
Staring at this a while, you might notice that you can solve this with a nested Table
Table[{i, j, k}, {i, 4}, {j, i, 4}, {k, j, 4}]
(* {{{{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 1, 4}}, {{1, 2,
2}, {1, 2, 3}, {1, 2, 4}}, {{1, 3, 3}, {1, 3, 4}}, {{1, 4,
4}}}, {{{2, 2, 2}, {2, 2, 3}, {2, 2, 4}}, {{2, 3, 3}, {2, 3,
4}}, {{2, 4, 4}}}, {{{3, 3, 3}, {3, 3, 4}}, {{3, 4, 4}}}, {{{4, 4, 4}}}} *)
If you look closer at the iterators i,j, and k you see how it works: You need 3 iterators because you want tuples of length 3 and you need to iterate to 4, because your list has length 4. If you now take the above outcome as positions in a list, you can create the result for a general (uncomparable) list:
Table[Part[{a, b, c, d}, {i, j, k}], {i, 4}, {j, i, 4}, {k, j, 4}]
(* {{{{a, a, a}, {a, a, b}, {a, a, c}, {a, a, d}}, {{a, b,
b}, {a, b, c}, {a, b, d}}, {{a, c, c}, {a, c, d}}, {{a, d,
d}}}, {{{b, b, b}, {b, b, c}, {b, b, d}}, {{b, c, c}, {b, c,
d}}, {{b, d, d}}}, {{{c, c, c}, {c, c, d}}, {{c, d, d}}}, {{{d, d, d}}}} *)
What's left is to do is to flatten the result appropriately and to create this Table dynamically for any list and any tuple-length:
f[l_List, n_] :=
With[{iter = {#2, #1, Length[l]} & @@@
Partition[Prepend[Array[Unique[] &, n], 1], 2, 1]},
Part[l, #] & /@
Flatten[Table @@ {iter[[All, 1]], Sequence @@ iter}, n - 1]
]
And now you can use the approach for any kind of list. Be careful, you have to ensure that the input list is sorted to your needs:
Sometime ago I posted a similar function (search comb) at
I copy and paste the function here. This function generates increasing number tuples. The idea is to first generate an expression like Table[{i[1],i[2], ...},{i[1],0,m}, {i[2], i[1], m}, ...], and then execute this expression.
comb[lenIn_, lenOut_] := Module[{i}, i[0] = 0;
Flatten[#, lenOut - 1] &@
With[{elem = i@# & /@ Range@lenOut,
ranges = Sequence @@ ({i[#], i[# - 1], lenIn - 1} & /@ Range@lenOut)},
Table[elem, ranges]]]
For example,
comb[4, 3]
{{0, 0, 0}, {0, 0, 1}, {0, 0, 2}, {0, 0, 3}, {0, 1, 1}, {0, 1, 2}, {0, 1, 3}, {0, 2, 2}, {0, 2, 3}, {0, 3, 3}, {1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}, {1, 3, 3}, {2, 2, 2}, {2, 2, 3}, {2, 3, 3}, {3, 3, 3}}
To better fit your question, one can write a helper function
f[lst_, n_] :=
Extract[Sort@lst, #] & /@ Map[{#} &, comb[Length@lst, n] + 1, {-1}]
For example,
f[{a, b, c}, 2]
{{a, a}, {a, b}, {a, c}, {b, b}, {b, c}, {c, c}}
EDIT: @halirutan has already posted an answer, with essentially the same algorithm. Sorry for my duplicate answer! But let me keep it from being deleted because of some minor difference between our solutions.
Select[Tuples[{1, 2, 3, 4}, 3], OrderedQ ] will do it...
Or generalized to take arguments Select[Tuples[#1, #2], OrderedQ] &[{1, 2, 3, 4}, 3]
