我有一个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.

解决方法:

用于以字典顺序生成一组唯一值的组合的相同(或几乎相同)算法可用于以字典顺序生成多集的组合.这样做可以避免重复数据删除的必要性,这是非常昂贵的,并且还避免了维护所有生成的组合的必要性.它确实需要对原始值列表进行排序.

以下简单实现在平均(和最差情况)时间O(n)中找到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()));

住在coliru