迭代大小为 k 的不同子集

Question

我有一个由 n 个整数组成的数组（不一定是不同的！），我想遍历所有大小为 k 的子集。但是我想排除所有重复的子集。

例如

array = {1,2,2,3,3,3,3}, n = 7, k = 2

那么我想要迭代的子集（每次一次）是：

{1,2},{1,3},{2,2},{2,3},{3,3}

这样做的有效算法是什么？递归方法是最有效/最优雅的吗？

如果您有特定于语言的答案，我将使用 C++。

Answer 1

用于生成按字典顺序排列的一组唯一值的组合的相同（或几乎相同）算法可用于生成按字典顺序排列的多组组合。这样做避免了重复数据删除的必要性，这是非常昂贵的，也避免了维护所有生成的组合的必要性。它确实要求对原始值列表进行排序。

下面的简单实现在平均（和最坏情况）时间 O( n ) 内找到n 个值的多组的下一个k组合。它需要两个范围：第一个范围是排序的k组合，第二个范围是排序的多重集。（如果任一范围未排序或第一个范围中的值不构成第二个范围的子（多）集，则行为未定义；不进行完整性检查。）

实际上只使用了第二个范围的结束迭代器，但我认为这使得调用约定有点奇怪。

template<typename BidiIter, typename CBidiIter,
         typename Compare = std::less<typename BidiIter::value_type>>
int next_comb(BidiIter first, BidiIter last,
              CBidiIter /* first_value */, CBidiIter last_value,
              Compare comp=Compare()) {
  /* 1. Find the rightmost value which could be advanced, if any */
  auto p = last;
  while (p != first && !comp(*(p - 1), *--last_value)) --p;
  if (p == first) return false;
  /* 2. Find the smallest value which is greater than the selected value */
  for (--p; comp(*p, *(last_value - 1)); --last_value) { }
  /* 3. Overwrite the suffix of the subset with the lexicographically smallest
   *    sequence starting with the new value */
  while (p != last) *p++ = *last_value++;
  return true;
}

应该清楚，步骤 1 和步骤 2 组合最多进行 O( n ) 次比较，因为n 个值中的每一个值最多用于一次比较。第 3 步最多复制 O( k ) 个值，我们知道k ≤ n。

在没有重复值的情况下，这可以改进为 O( k )，方法是将当前组合作为迭代器的容器维护到值列表而不是实际值中。这也将避免复制值，代价是额外的取消引用。此外，如果我们缓存将每个值迭代器与迭代器关联到下一个最大值的第一个实例的函数，我们可以消除步骤 2 并将算法简化为 O( k )，即使对于重复值也是如此。如果有大量重复并且比较昂贵，这可能是值得的。

这是一个简单的使用示例：

std::vector<int> values = {1,2,2,3,3,3,3};
/* Since that's sorted, the first subset is just the first k values */
const int k = 2;
std::vector<int> subset{values.cbegin(), values.cbegin() + k};

/* Print each combination */
do {
  for (auto const& v : subset) std::cout << v << ' ';
  std::cout << '\n';
} while (next_comb(subset.begin(),  subset.end(),
                   values.cbegin(), values.cend()));

住在科利鲁