与重复的组合

Question

我正在使用 Mathematica 7 并使用 Combinatorica 包函数，我可以从元素列表中获取特定数量的所有组合，其中顺序无关紧要并且没有重复。例如：

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 出现的次数。然后，任务是找到 4 个非负整数加起来为 3 的所有可能组合。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 和 Tuple 之间的时间比较（以日志秒为单位）

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]

_{（来源：yaroslavvb.com）}

Answer 2

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

Answer 3

这是一个简单的解决方案，它利用 Mathematica 的内置函数 Subsets，因此在简单性和性能之间取得了很好的平衡。 [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}}

Answer 4

High Performance Mark 给出的优雅方法的一个细微变化：

Select[Tuples[{a, b, c, d}, 3], OrderedQ]

排列稍微更通用（但不是您正在寻找的？）

例如：

Select[Permutations[
  Sort@Flatten@ConstantArray[{a, b, c, d}, {3}], {2, 3}], OrderedQ]

给出以下

编辑：

Select[Tuples[Sort@{a, b, d, c}, 3], OrderedQ]

可能更好

Edit-2

当然，也可以使用案例。例如

Cases[Permutations[
  Sort@Flatten@ConstantArray[{a, b, d, c}, {3}], {2, 3}], _?OrderedQ]

编辑3。

如果列表包含重复元素，这两种方法将会有所不同。输出来自
例如，以下（方法 2）将包含重复项（可能需要也可能不需要）：

Select[Tuples[{a, b, c, d, a}, 3], OrderedQ]

它们可以很容易地被删除：

Union@Select[Tuples[{a, b, c, d, a}, 3], OrderedQ]

以下计算结果为“True”（从提供给方法 2 的列表中删除重复元素，并对方法 1（高性能标记方法）生成的列表进行排序：

lst = RandomInteger[9, 50]; 
Select[Union@Sort@Tuples[lst, 3], OrderedQ] == 
 Sort@DeleteDuplicates[Map[Sort, Tuples[lst, 3]]]

如下所示（从方法 2 的输出中删除重复项，对方法 1 的输出进行排序）：

lst = RandomInteger[9, 50]; 
Union@Select[Sort@Tuples[lst, 3], OrderedQ] == 
 Sort@DeleteDuplicates[Map[Sort, Tuples[lst, 3]]]

对此感到抱歉！