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。 p>

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

例如，S = {苹果、香蕉、chirimoya、枣}(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查找集合的排列在多重集上同样有效，尽管如果多重集有很多重复项，则它不是最佳的。