0

したがって、次のような配列が与えられた場合

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++ でどのように実装できるかはよくわかりません

したがって、基本的に私が求めているのは、バイナリカウントを使用してパワーセットを生成するにはどうすればよいかということです。

パワーセットを生成する他の方法も大歓迎です!

4

3 に答える 3

5

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 }

最下位ビットを最初のセット要素に対応させるのが一般的な規則であることに注意してください。

null セット s = 0 を省略していることにも注意してください。

64 要素を超えるセット (つまりuint64_t) を使用する必要がある場合は、より良いアプローチが必要になります。上記の方法を拡張して複数の整数要素を使用するstd::bitsetかstd::vector<bool>、 or を使用するか、@Yochai の回答 ( を使用std::next_permutation)のようなものを使用できます。 .

于 2014-08-26T08:21:44.073 に答える
0

実際にセットを作成するのは非常に簡単です。ビットごとの操作>>=を使用&して、一度に少しずつテストするだけです。入力ベクトル/配列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]);
于 2014-08-26T08:55:42.820 に答える
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));
}

実際の例

于 2014-08-26T09:27:09.800 に答える