Использование двоичного подсчета для подсчета всех подмножеств массива

Так что, если мне дают массив, такой как

a = {1, 2, 3}

Мы знаем, что данные подмассивы (не смежные) являются (это представляет набор мощности)

{1} {2} {3} {1,2,3} {1,2} {1,3} {2,3}

Я также знаю, что эти подмножества могут быть представлены путем подсчета в двоичном

000 -> 111 (0 to 7), where each 1 bit means we 'use' this value from the array
e.g. 001 corresponds to the subset {3}

Я знаю, что этот метод может каким-то образом использоваться для генерации всех подмножеств, но я не совсем уверен, как это можно реализовать в C ++

Итак, в основном я спрашиваю, как (если это возможно) двоичный счет можно использовать для генерации наборов мощности?

Любые другие методы для создания набора мощности также приветствуются!

0

Решение

Для вашего примера с 3 установленными элементами вы можете просто сделать это:

for (s = 1; s <= 7; ++s)
{
// ...
}

Вот демонстрационная программа:

#include <iostream>

int main()
{
const int num_elems = 3;                      // number of set elements
const int elems[num_elems] = { 1, 2, 3 };     // mapping of set element positions to values

for (int s = 1; s < (1 << num_elems); ++s)    // iterate through all non-null sets
{
// print the set
std::cout << "{";
for (int e = 0; e < num_elems; ++e)       // for each set element
{
if (s & (1 << e))                     // test for membership of set
{
std::cout << " " << elems[e];
}
}
std::cout << " }" << std::endl;
}
return 0;
}

Скомпилируйте и протестируйте:

$ g++ -Wall sets.cpp && ./a.out

{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }

Обратите внимание, что по общему правилу младший значащий бит соответствует первому элементу набора.

Также обратите внимание, что мы опускаем нулевой набор, s = 0, так как вы, кажется, не хотите это включать.

Если вам нужно работать с наборами размером более 64 элементов (т.е. uint64_t) тогда вам понадобится лучший подход — вы можете либо расширить вышеуказанный метод для использования нескольких целочисленных элементов, либо использовать std::bitset или же std::vector<bool>или используйте что-то вроде ответа @ Yochai (используя std::next_permutation).

4

Другие решения

На самом деле создание наборов довольно просто — просто используйте побитовые операции >>= а также & чтобы проверить немного за один раз. Предполагая входной вектор / массив a[] известно, что имеет 3 элемента и, следовательно, производит 7 векторных выходных данных:

std::vector<std::vector<T>> v(7);
for (int n = 1; n <= 7; ++n)   // each output set...
for (int i = 0, j = n; j; j >>= 1, ++i)  // i moves through a[i],
// j helps extract bits in n
if (j & 1)
v[n-1].push_back(a[i]);
0

Для размера времени компиляции вы можете использовать bitset, что-то вроде:

template <std::size_t N>
bool increase(std::bitset<N>& bs)
{
for (std::size_t i = 0; i != bs.size(); ++i) {
if (bs.flip(i).test(i) == true) {
return true;
}
}
return false; // overflow
}

template <typename T, std::size_t N>
void display(const std::array<T, N>& a, const std::bitset<N>& bs)
{
std::cout << '{';
const char* sep = "";

for (std::size_t i = 0; i != bs.size(); ++i) {
if (bs.test(i)) {
std::cout << sep << a[i];
sep = ", ";
}
}
std::cout << '}' << std::endl;
}

template <typename T, std::size_t N>
void display_all_subsets(const std::array<T, N>& a)
{
std::bitset<N> bs;

do {
display(a, bs);
} while (increase(bs));
}

Живой пример

0
По вопросам рекламы [email protected]