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

下面的简单实现找到了平均（和最坏情况）时间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（ ķ ）值，而我们知道，
ķ ≤ ñ 。

在不重复任何值的情况下，可以通过将当前组合作为迭代器的容器（而不是实际值）存储在值列表中，将其改进为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()));

活在大肠杆菌上