用于生成按字典顺序排列的一组唯一值的组合的相同（或几乎相同）算法可用于生成按字典顺序排列的多重集的组合。这样做可以避免重复数据删除的必要性（这是非常昂贵的），并且还避免了维护所有生成的组合的必要性。它确实需要对原始值列表进行排序。
下面的简单实现找到了下一个k- 多组的组合n平均（和最坏情况）时间 O(n）。它需要两个范围：第一个范围是排序的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()));
Live on coliru
