Итеративно рассчитать набор мощности набора или вектора
Хотя существует множество примеров того, как генерировать фактический набор мощности набора, я не могу найти что-либо об итеративном (как в std::iterator) Генерация мощности. Причиной, по которой я был бы признателен за такой алгоритм, является размер моего базового набора. Поскольку набор мощности n-элементного набора имеет 2 ^ n элементов, я бы быстро исчерпал память, когда фактически вычислял набор. Итак, есть ли способ создать итератор для набора мощности данного набора? Это вообще возможно?
- Если это будет проще, итератор, который создает наборы
intБыло бы хорошо — я мог бы использовать их в качестве индексов для фактического набора / вектора. - Как я на самом деле работаю над
std::vectorпроизвольный доступ был бы возможен при необходимости
Решение
С помощью for_each_combination от Комбинации и перестановки можно легко перебрать всех членов набора мощности std::vector<AnyType>, Например:
#include <vector>
#include <iostream>
#include "../combinations/combinations"
int
main()
{
std::vector<int> v{1, 2, 3, 4, 5};
std::size_t num_visits = 0;
for (std::size_t k = 0; k <= v.size(); ++k)
for_each_combination(v.begin(), v.begin()+k, v.end(),
[&](auto first, auto last)
{
std::cout << '{';
if (first != last)
{
std::cout << *first;
for (++first; first != last; ++first)
std::cout << ", " << *first;
}
std::cout << "}\n";
++num_visits;
return false;
});
std::cout << "num_visits = " << num_visits << '\n';
}
Это посещает каждого члена группы власти этого vectorи выполняет функтор, который просто считает количество посещений и распечатывает текущий набор мощности:
{}
{1}
{2}
{3}
{4}
{5}
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{2, 3}
{2, 4}
{2, 5}
{3, 4}
{3, 5}
{4, 5}
{1, 2, 3}
{1, 2, 4}
{1, 2, 5}
{1, 3, 4}
{1, 3, 5}
{1, 4, 5}
{2, 3, 4}
{2, 3, 5}
{2, 4, 5}
{3, 4, 5}
{1, 2, 3, 4}
{1, 2, 3, 5}
{1, 2, 4, 5}
{1, 3, 4, 5}
{2, 3, 4, 5}
{1, 2, 3, 4, 5}
num_visits = 32
Синтаксис, который я использовал выше, это C ++ 14. Если у вас есть C ++ 11, вам нужно изменить:
[&](auto first, auto last)
чтобы:
[&](std::vector<int>::const_iterator first, std::vector<int>::const_iterator last)
И если вы находитесь в C ++ 98/03, вам придется написать функтор или функцию для замены лямбда-выражения.
for_each_combination Функция не выделяет дополнительной памяти. Это все сделано путем обмена членами vector в диапазон [v.begin(), v.begin()+k), В конце каждого звонка for_each_combination вектор остается в исходном состоянии.
Если по какой-то причине вы хотите «выйти» из for_each_combination рано, просто вернись true вместо false,
Другие решения