Същият (или почти същият) алгоритъм, който се използва за генериране на комбинации от набор от уникални стойности в лексикографски ред, може да се използва за генериране на комбинации от множество в лексикографски ред. Правейки го по този начин, избягвате необходимостта от дедупликация, което е ужасно скъпо, и също така избягвате необходимостта от поддържане на всички генерирани комбинации. Това изисква първоначалният списък със стойности да бъде сортиран.
Следната проста реализация намира следващата 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) стойности и знаем, че kn.
Това може да се подобри до 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
person
rici
schedule
28.05.2015
{2,2}
и{3,3}
. - person Barry   schedule 28.05.2015std::next_permutation
можеше да е част от отговор. Отговорът на този въпрос включва броене по ограничен начин (само увеличаващи се последователности от цифри), но не мисля, че стандартната библиотека помага с това. - person Cheers and hth. - Alf   schedule 28.05.2015