10
$\begingroup$

Suppose I have a list

lis={a,b,c,d,e,f};

Is there a way to get all the combination of 3 elements (without order) from it? I try to use

Flatten[Permutations /@ Subsets[lis, {3}], 1]

But it not contains the repeated elements, that is I want the elements such as {a,a,a} be included also.

Improve this question
$\endgroup$
2
  • $\begingroup$ @george2079 Tuples don't ignore order. I had this problem earlier today and wound up writing Join[Subsets[extensions, {2}] , {#, #} & /@ extensions] I hope I missed something... $\endgroup$
    – V.E.
    Commented Sep 18, 2016 at 2:35
  • 2
    $\begingroup$ Sort/@Tuples//Union ? $\endgroup$
    – george2079
    Commented Sep 18, 2016 at 2:52

3 Answers 3

Reset to default
15
$\begingroup$

Using Subsets you can avoid deleting many duplicates

Multisets[s_List, n_Integer] := With[{u = Range[0, n - 1]},
        s[[# - u]] & /@ Subsets[Range[Length[s] + n - 1], {n}]]
Multisets[{a, b, c, d, e}, 3]

This vectorized version is probably faster:

Multisets[s_List, n_Integer] := Partition[s[[Flatten[Transpose[Subsets[
    Range[Length[s] + n - 1], {n}]] - Range[0, n - 1], {2, 1}]]], n]
Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Really nice method! $\endgroup$
    – Mr.Wizard
    Commented Sep 18, 2016 at 13:28
  • $\begingroup$ this wins the timing tests.. ( the first form beats the second in some cases for long input lists ) $\endgroup$
    – george2079
    Commented Sep 19, 2016 at 15:24
  • $\begingroup$ for example : {{1,1},{1,2},{1,3},{2,2},{2,3},{3,3}} = (# - {1,2})& /@ {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}} $\endgroup$
    – Hayashi Yoshiaki
    Commented May 25 at 23:07
6
$\begingroup$

There are more solutions maybe this is the shortest.

Union[Sort /@ Tuples[Table[{a, b, c, d, e}, {3}]]]
(* {{a, a, a}, {a, a, b}, {a, a, c}, {a, a, d}, {a, a, e}, {a, b,
   b}, {a, b, c}, {a, b, d}, {a, b, e}, {a, c, c}, {a, c, d}, {a, c, 
  e}, {a, d, d}, {a, d, e}, {a, e, e}, {b, b, b}, {b, b, c}, {b, b, 
  d}, {b, b, e}, {b, c, c}, {b, c, d}, {b, c, e}, {b, d, d}, {b, d, 
  e}, {b, e, e}, {c, c, c}, {c, c, d}, {c, c, e}, {c, d, d}, {c, d, 
  e}, {c, e, e}, {d, d, d}, {d, d, e}, {d, e, e}, {e, e, e}} *)
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This can be shortened to Union[Sort /@ Tuples[{a, b, c, d, e}, {3}]] $\endgroup$
    – Bob Hanlon
    Commented Sep 18, 2016 at 15:33
  • $\begingroup$ this is good for readability so long as the list is short, but note you'll run out of memory quickly for longer lists.. $\endgroup$
    – george2079
    Commented Sep 19, 2016 at 14:52
3
$\begingroup$

another approach:

unsortedtuples[input_,n_] := 
 Module[{p}, 
  Nest[Flatten[
     Function[{subl}, p = Position[input, Last@subl][[1, 1]]; 
       Append[subl, #] & /@ input[[;; p]]] /@ #, 1] &, 
   Transpose@{input}, n-1]]
unsortedtuples[{a, b, c, d},4]


 
        {{a, a, a, a}, {b, a, a, a}, {b, b, a, a}, {b, b, b, a}, 
         {b, b, b, b}, {c, a, a, a}, {c, b, a, a}, {c, b, b, a}, 
         {c, b, b, b}, {c, c, a, a}, {c, c, b, a}, {c, c, b, b},
         {c, c, c, a}, {c, c, c, b}, {c, c, c, c}, {d, a, a, a},
         {d, b, a, a}, {d, b, b, a}, {d, b, b, b}, {d, c, a, a},
         {d, c, b, a}, {d, c, b, b}, {d, c, c, a}, {d, c, c, b}, 
         {d, c, c, c}, {d, d, a, a}, {d, d, b, a}, {d, d, b, b},
         {d, d, c, a}, {d, d, c, b}, {d, d, c, c}, {d, d, d, a},
         {d, d, d, b}, {d, d, d, c}, {d, d, d, d}}

note this assumes no repeated elements in the input. (Probably just do Union on the input if that's an issue, otherwise I'm not sure what the result should be )

Improve this answer
$\endgroup$

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