2

我意识到有很多关于组合学和枚举的问题，但我四处搜索并没有找到任何与我所追求的东西特别相关的东西。如果我错过了什么，请指出它，问题可以结束。

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

我希望我的措辞正确。如果我没有，一个简单的例子。
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 将使用标准组合枚举生成，或者从每个级别的源集中删除那些已选择的元素，或者仅从原始集中枚举并跳过之前已包含元素的情况.

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

4

1 回答 1

2

您的问题正是枚举多集排列的问题。（假设你的 k i是有序的）。

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

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

例如，S = {apple、banana、chirimoya、date} (N = 4)。我们取 k 1 = 2 和 k 2 = 1 并加上 k 3 = 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}}

用于查找集合排列的标准算法在多集合上也同样适用，尽管如果多集合有很多重复项，它就不是最优的。

于 2012-10-22T16:21:40.390 回答