部分集合の列挙 (Enumerate Subset)
(Other/EnumerateSubset.hpp)

• View this file on GitHub
• Last update: 2023-07-16 21:56:51+09:00
• Include: #include "Other/EnumerateSubset.hpp"

概要

bitの立っている箇所を集合の要素として，その集合の部分集合を列挙して返す．
つまり，2進表記でbit=11001と表せるとき，
返すのは{11001, 11000, 10001, 10000, 01001, 01000, 00001, 00000}である．

有名な事実として，N個の集合の全ての部分集合において部分集合を列挙，つまり
for i=0 to (1«N)-1
EnumerateSubset(i)
をすると，計算量はO(3^N)である．

Verified with

• test/AOJ_1379.test.cpp

Code

vector< int > enumerate_subset(int S)
{
    vector< int > ret;
    int sub = S;
    while (sub > 0)
    {
        ret.push_back(sub);
        sub = (sub - 1) & S;
    }
    return ret;
}

#line 1 "Other/EnumerateSubset.hpp"
vector< int > enumerate_subset(int S)
{
    vector< int > ret;
    int sub = S;
    while (sub > 0)
    {
        ret.push_back(sub);
        sub = (sub - 1) & S;
    }
    return ret;
}

Back to top page