algorithm - 如何从单个集合中枚举组合的组合

Question

我意识到有很多关于组合数学和枚举的问题，但我四处搜索并没有发现任何与我所追求的具体相关的问题。如果我遗漏了什么，请指出，问题可以关闭。

因此，假设我们有一组 N 个元素，并且有 x 个正整数 k1,...,kx，其中 Sum(k1,...,kx) <= N。我想列举所有的方法可以从 N 的原始集合中选择(无需替换)x 个给定大小的子集。

我希望我的措辞是正确的。如果我没有，一个简单的例子。
N = 4, x = 2, k1 = 2, k2 = 1。

我们应该枚举

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

在一般情况下，我认为的总数是:

C(N, k1) * C(N - k1, k2) * ... * C(N - Sum(k1,...,kn-1), kn)。

我最初的猜测是，使用堆栈可以相当轻松地完成此操作。在每个堆栈级别 i 子集 ki 将使用标准组合枚举生成，或者从每个级别的源集中删除那些已被选择的元素，或者只是从原始集中枚举并跳过之前包含元素的情况.

我的问题，是否有更快/更优雅的解决方案？

Answer 1

您的问题正是枚举多重集排列的问题。 (假设您的 k_i 已订购)。

首先，请注意该问题与 Σk = N 时的问题完全等价，因为如果 Σk < N，我们可以简单地添加 k_x+1，其值为 N - Σk。

现在，将原始集合 S 的元素按任意固定顺序放置，并生成由 k₁ 个 1、k₂ 个 2、k 个组成的多重集的每个排列₃ 3，... k_x x。这个多重集具有与 S 相同的大小 (N)，因为 k_i 的总和为 N。我们通过将 S 中的每个元素分配给其索引对应的子集来创建 S 的分区多重集排列中的值。

例如，S = {apple, banana, chirimoya, date} (N = 4)。我们取 k₁ = 2 和 k₂ = 1 并加上 k₃ = 1 使总和为 4。(我们只是忽略分配给子集 3) 的元素。现在我们枚举多重集 1 1 2 3 的排列(其中有两个 1，一个 2，一个 3，对应于 k):

1 1 2 3    1 2 3 1    2 1 1 3    3 1 1 2
1 1 3 2    1 3 1 2    2 1 3 1    3 1 2 1
1 2 1 3    1 3 1 1    2 3 1 1    3 2 1 1

我们将这些转换回 S 的分区。例如，取 1 3 1 2:

apple     1 -> subset 1
banana    3 -> unused
chirimoya 1 -> subset 1
date      2 -> subset 2

所以我们有 {{apple, chirimoya}, {date}}

standard algorithm寻找一个集合的排列在多重集上同样有效，尽管如果多重集有很多重复，它不是最佳的。