c - 我们如何计算多重集的 r 组合？

Question

问题

定义 multiset 的拆分M 是一组大小相等的有序多集对，其并集为 M。

我们如何计算多重集的 split ？

讨论

这个问题源于this one .

这个问题与计算具有 2r 个元素的多重集的 r 组合的数量相同，解决方案在 Richard A. Brualdi，第二版，1992 年，Prentice-Hall, Inc. 的 Introductory Combinatorics 的第 6.2 节中给出了解决方案。它们是相同的，请注意在 2r 个元素的多重集 M 的任何 r 组合 X 和拆分 (X, Y) 之间存在 1-1 对应关系，其中 Y 是 M 中不在 X 中的所有元素，即, Y = M−X。

Brualdi 使用 inclusion-exclusion principle 的解决方案为数学家所熟知，适用于算法实现。

尽管它为数学家所熟知，但只是部分回答了here at Mathematics Stack Exchange和 here at Quora .

Answer 1

当然，原始问题与计算大小为 2r 的多集的 r 组合的问题是同构的。

作为包含-排除公式(当然具有分析值(value)，但可能具有较小的算法值(value))的替代方案，我们可以构造一个递归解决方案，它计算所有 k 值的集合的 k 组合的计数，使用递归算法中使用的递归方法非常相似，用于计算二项式系数 C(n,k)，即一组 n 个元素的 k 组合的计数。

假设我们将多重集表示为大小为 n(其中 n = 2r)的排序 vector V。 (从技术上讲，它不必排序；它被“聚集”就足够了，这样所有相同的元素都是连续的。但是，最简单的方法是对 vector ​​进行排序。)我们想要产生该 vector 的所有唯一 k 组合。所有这些组合都具有以下两种形式之一:

“选择第一个元素”。该组合以 V1 开始，并以 (V2, V3, ..., Vn) 的 (k-1) 组合继续。

“跳过第一个元素”。该组合是 (Vi, Vi+1, ... Vn) 的 k 组合，其中 i 是满足 Vi ≠ V1 的最小索引。 (我们需要跳过与第一个元素相同的所有元素以避免重复。)

这里与二项式递归的唯一区别是在第二个选项中使用了索引 i；如果集合没有重复的元素，这将减少到 i=2，从而产生递归 C(n, k) = C(n - 1, k - 1) + C(n - 1, k)。

这种递归的简单实现将花费指数时间，因为每次计算都需要两次递归调用；但是，只有二次调用的唯一调用，因此可以通过内存或动态编程将计算减少到二次时间。下面的解决方案使用动态规划，因为这只需要线性空间。 (内存需要二次空间，因为子问题的数量是二次的。)

动态规划解决方案通过计算 vector 的连续后缀的 k 组合数来反转递归。它只需要保留两个后缀的值:前一个后缀和具有不同第一个元素的前一个后缀，对应于上述递归的第一个和第二个选项所需的计数。 (实际代码使用前缀而不是后缀，但绝对没有区别。)

作为一个小的优化，我们只计算 k 值在 0 和 ⌈n/2⌉ 之间的 k 组合的计数。与二项式系数一样，计数是对称的:k-组合的数量等于 (n-k)-组合的数量，因为每个 k-组合对应于一个唯一的 (n-k)-组合，其中包含所有未选择的元素。基于我们最后只需要一个计数这一事实，可以进行额外的优化，但额外的复杂性只会掩盖基本算法。

解是 O(n2) 的事实有点烦人，但由于 n 通常是一个很小的数字(否则计数将是天文数字)，计算时间似乎是合理的。毫无疑问，还有进一步的优化可能，而且很可能存在次二次算法。

这是 C 中的一个基本实现(使用字符串数组):

/* Given a *sorted* vector v of size n, compute the number of unique k-combinations
 * of the elements of the vector for values of k between 0 and (n/2)+1.
 * The counts are stored in the vector r, which must be large enough.
 * Counts for larger values of k can be trivially looked up in the returned
 * vector, using the identity r[k] == r[n - k].
 * If v is not sorted, the result will be incorrect. The function does not
 * check for overflow, but the results will be correct modulo (UINTMAX + 1)
 */
void multicomb(const char** v, size_t n, uintmax_t* r) {
  size_t lim = n / 2 + 1;
  // Prev retains the counts for the previous prefix ending with
  // a different element
  uintmax_t prev[lim];
  // If there are no elements, there is 1 0-combination and no other combinations.
  memset(r, 0, sizeof prev);
  r[0] = 1;
  // Iterate over the unique elements of v
  for (size_t k = 0; k < n; ) {
    // Save the counts for this prefix
    memcpy(prev, r, sizeof prev);
    // Iterate over the prefixes with the same ending value
    do {
      for (size_t i = lim - 1; i > 0; --i)
        r[i] = r[i - 1] + prev[i];
    } while (++k < n && strcmp(v[k - 1], v[k]) == 0);
  };
}

与OP的自我回答中的解决方案相比，此版本:

稍后溢出，因为它只取决于加法。 (没有除法的事实也使得计算模数的计数变得更加容易。)

需要二次时间而不是指数时间。