Ответ 1
http://howardhinnant.github.io/combinations.html
Следующие общие алгоритмы позволяют клиенту посещать каждую комбинацию или изменение последовательности элементов длины N, r в момент времени.
Пример использования:
std::vector<std::vector<int>> box;
std::vector<int> v(N);
std::iota(begin(v), end(v), 1);
for_each_combination(begin(v), begin(v) + M, end(v), [](auto b, auto e) {
box.emplace_back(b, e);
return false;
});
В приведенном выше коде просто показано, как вставлять каждую комбинацию в box, но вы, вероятно, не хотите этого делать: предполагая, что box является просто посредником и ваша фактическая работа затем использует его в другом месте, вы можете избежать посредника и просто выполнять любую работу, которая вам нужна непосредственно в теле функтора.
Здесь полный рабочий пример, используя код из предоставленной ссылки.
Поскольку вам нужны комбинации с повторением, а не с комбинациями. Вот пример реализации этого над for_each_combination():
template<typename Func>
void for_each_combination_with_repetition(int categories, int slots, Func func) {
std::vector<int> v(slots + categories - 1);
std::iota(begin(v), end(v), 1);
std::vector<int> indices;
for_each_combination(begin(v), begin(v) + slots, end(v), [&](auto b, auto e) {
indices.clear();
int last = 0;
int current_element = 0;
for(;b != e; ++last) {
if (*b == last+1) {
indices.push_back(current_element);
++b;
} else {
++current_element;
}
}
func(begin(indices), end(indices));
return false;
});
}
Статья wikipedia на комбинациях показывает хорошую иллюстрацию того, что это делает: она получает все комбинации (без повторения) чисел [0, N + M - 1), а затем ищет "пробелы" в результатах. Разрывы представляют собой переходы от повторений одного элемента к повторениям следующего.
Функтору, которому вы передаете этот алгоритм, задан диапазон, содержащий индексы в коллекцию, содержащую элементы, которые вы объединяете. Например, если вы хотите получить все наборы из трех элементов из набора {x, y}, то вы хотите получить результаты {{x, x, x}, {x, x, y}, {x, y, y}, {y, y, y}}, и этот алгоритм представляет это, возвращая диапазоны индексов в (упорядоченное) множество {x, y}: {{0,0,0}, {0,0,1}, {0,1,1}, {1,1,1}}.
Таким образом, чтобы использовать это, у вас есть вектор или что-то, что содержит ваши элементы, и используйте диапазоны, созданные этим алгоритмом, как индексы в этом контейнере. Однако в вашем случае, поскольку элементы - это всего лишь цифры от 1 до N, вы можете напрямую использовать индексы, добавляя один к каждому индексу:
for_each_combination_with_repetition(N, M, [&](auto b, auto e) {
for(; b != e; ++b) {
int index = *b;
std::cout << index + 1 << " ";
}
std::cout << '\n';
});
Альтернативная реализация может возвращать векторы, которые представляют собой подсчеты каждой категории. Например. более ранние результаты {{x, x, x}, {x, x, y}, {x, y, y}, {y, y, y}} могут быть представлены: {{3,0} {2, 1}, {1,2}, {0,3}}. Изменение реализации для создания этого представления выглядит следующим образом:
template<typename Func>
void for_each_combination_with_repetition(int categories, int slots, Func func) {
std::vector<int> v(slots + categories - 1);
std::iota(begin(v), end(v), 1);
std::vector<int> repetitions(categories);
for_each_combination(begin(v), begin(v) + slots, end(v), [&](auto b, auto e) {
std::fill(begin(repetitions), end(repetitions), 0);
int last = 0;
int current_element = 0;
for(;b != e; ++last) {
if (*b == last+1) {
++repetitions[current_element];
++b;
} else {
++current_element;
}
}
func(begin(repetitions), end(repetitions));
return false;
});
}