Как избежать этого для беспорядка в С++?

Ответ 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;
    });
}

Ответ 2

Вы можете использовать рекурсию для поиска всех подмножеств. Это, вероятно, может быть улучшено стилистически, но здесь можно быстро решить проблему:

std::vector<std::set<int>> subsets(std::vector<int> x)
{
    if (x.size() == 0)
        return { std::set<int>() };
    else
    {
        int last = x.back();
        x.pop_back();

        auto sets = subsets(x);
        size_t n = sets.size();

        for (size_t i = 0; i < n; i++)
        {
            std::set<int> s = sets[i];
            s.insert(last);
            sets.push_back(std::move(s));
        }

        return sets;
    }
}

Это удваивает количество ответов на каждом этапе рекурсии: количество подмножеств равно 2 ^ n, как и ожидалось.

Вы можете заменить std::set на std::vector, если хотите.