重复的组合

Question

我正在使用Mathematica 7和一个combinatorica包函数我可以从一个元素列表获得一定数量的所有组合,其中顺序无关紧要且没有重复.eg:

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

我无法找到一个功能,这将使我一定数目的所有组合从元素,其中的顺序并不重要,那里的名单是重复的.即,上面的示例将在输出中包含{a,a,b},{a,a,a},{b,b,b}等元素.

它可能需要自定义功能.如果我能拿出一个,我会发一个答案但是现在我没有看到明显的解决方案.

编辑:理想情况下,输出将不包含组合的重复,例如元组[{a,b,c,d},3]将返回包含两个元素的列表,如{a,a,b}和{b,a,a从组合的角度来看,它们是相同的.

Answer 1

您可以将每个组合编码为{na,nb,nc,nd}na给出的次数a.然后,任务是找到加起来为3的4个非负整数的所有可能组合.IntegerPartition给出了一种快速的方法来生成所有这样的组合,其中顺序无关紧要,并且您遵循它Permutations来考虑不同的顺序

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]

只是为了好玩,这里是针对此任务的IntegerPartitions和Tuples之间的时序比较,以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]

http://yaroslavvb.com/upload/save/tuples-vs-partitions.png

Answer 2

DeleteDuplicates[Map[Sort, Tuples[{a, b, c, d}, 3]]]

Answer 3

这是一个简单的解决方案，它利用了 Mathematica 的内置函数子集，因此在简单性和性能之间取得了很好的平衡。[n+k-1] 的 k 子集和 [n] 的 k 组合之间有一个简单的双射，重复。此功能将子集更改为重复组合。

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

所以

CombWithRep[4,2]

产量

{{1,1},{1,2},{1,3},{1,4},{2,2},{2,3},{2,4},{3,3},{3,4},{4,4}}