Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.)

share|improve this question
    
related question on StackOverflow where High Performance Mark gives a nice answer –  TomD Feb 14 at 11:53
    
possible duplicate of How to delete mirror symmetric point pair efficiently –  Artes Feb 14 at 12:32
add comment

3 Answers 3

up vote 4 down vote accepted

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:

Mathematica graphics

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:

Mathematica graphics

share|improve this answer
add comment

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]

share|improve this answer
add comment

Sometime ago I posted a similar function (search comb) at

Shuffle product of two lists

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.