Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Combinations with repetition

I'm using Mathematica 7 and with a combinatorica package function I can get all combinations of a certain number from a list of elements where the order doesn't matter and there is no repetition.e.g:

in: KSubsets[{a, b, c, d}, 3]
out: {{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}}

I cannot find a function that will give me all combinations of a certain number from a list of elements where the order doesn't matter and there is repetition. i.e. the above example would include elements like {a,a,b},{a,a,a},{b,b,b}...etc in the output.

It may require a custom function. If I can come up with one I will post an answer but for now I don't see an obvious solution.

Edit: Ideally the output will not contain duplication of a combination e.g. Tuples[{a, b, c, d}, 3] will return a list that contains two elements like {a,a,b} and {b,a,a} which from a combinations point of view are the same.

like image 605
dbjohn Avatar asked Nov 30 '10 22:11

dbjohn


People also ask

Can combinations have repetition?

In both permutations and combinations, repetition is not allowed.

How many combinations of 4 items have no repeats?

The number of possible combinations with 4 numbers without repetition is 15. The formula we use to calculate the number of n element combinations when repetition is not allowed is 2n - 1.

What is the formula for combinations with repetition?

How to calculate combinations with repetition? Input the values in the following formula: C'(n,r) = (r+n-1)! / (r!( n-1)!) .

What does combination with repetition mean?

Combinations with repetition A combination with repetition of objects from is a way of selecting objects from a list of. . The selection rules are: the order of selection does not matter (the same objects selected in different orders are regarded as the same combination); each object can be selected more than once.


3 Answers

You can encode each combination as {na,nb,nc,nd} where na gives the number of times a appears. The task is then to find all possible combinations of 4 non-negative integers that add up to 3. IntegerPartition gives a fast way to generate all such such combinations where order doesn't matter, and you follow it with Permutations to account for different orders

vars = {a, b, c, d};
len = 3;
coef2vars[lst_] := 
 Join @@ (MapIndexed[Table[vars[[#2[[1]]]], {#1}] &, lst])
coefs = Permutations /@ 
   IntegerPartitions[len, {Length[vars]}, Range[0, len]];
coef2vars /@ Flatten[coefs, 1]

Just for fun, here's timing comparison between IntegerPartitions and Tuples for this task, in log-seconds

approach1[numTypes_, len_] := 
  Union[Sort /@ Tuples[Range[numTypes], len]];
approach2[numTypes_, len_] := 
  Flatten[Permutations /@ 
    IntegerPartitions[len, {numTypes}, Range[0, len]], 1];

plot1 = ListLinePlot[(AbsoluteTiming[approach1[3, #];] // First // 
       Log) & /@ Range[13], PlotStyle -> Red];
plot2 = ListLinePlot[(AbsoluteTiming[approach2[3, #];] // First // 
       Log) & /@ Range[13]];
Show[plot1, plot2]


(source: yaroslavvb.com)

like image 61
Yaroslav Bulatov Avatar answered Nov 10 '22 05:11

Yaroslav Bulatov


DeleteDuplicates[Map[Sort, Tuples[{a, b, c, d}, 3]]]
like image 41
High Performance Mark Avatar answered Nov 10 '22 03:11

High Performance Mark


Here's a simple solution that takes advantage of Mathetmatica's built-in function Subsets and thus is a nice balance between simplicity and performance. There is a simple bijection between k-subsets of [n+k-1] and k-combinations of [n] with repetition. This function changes subsets into combinations with repetition.

CombWithRep[n_, k_] := #-(Range[k]-1)&/@Subsets[Range[n+k-1],{k}]

So

CombWithRep[4,2]

yields

{{1,1},{1,2},{1,3},{1,4},{2,2},{2,3},{2,4},{3,3},{3,4},{4,4}}
like image 32
Jeffrey Liese Avatar answered Nov 10 '22 04:11

Jeffrey Liese