8
$\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.

$\endgroup$
  • $\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. Sep 18 '16 at 2:35
  • 1
    $\begingroup$ Sort/@Tuples//Union ? $\endgroup$ – george2079 Sep 18 '16 at 2:52
12
$\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]
$\endgroup$
  • 2
    $\begingroup$ Really nice method! $\endgroup$ – Mr.Wizard Sep 18 '16 at 13:28
  • $\begingroup$ this wins the timing tests.. ( the first form beats the second in some cases for long input lists ) $\endgroup$ – george2079 Sep 19 '16 at 15:24
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}} *)
$\endgroup$
  • $\begingroup$ This can be shortened to Union[Sort /@ Tuples[{a, b, c, d, e}, {3}]] $\endgroup$ – Bob Hanlon Sep 18 '16 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 Sep 19 '16 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 )

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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