ビットで表された部分集合の全探索(蟻本p144)

  • たとえば8人集合 01101101
  • 1が生きているとする
  • 生きている中から部分集合の選び方を全探索する
  • 今回の場合、1が5つあるので、25=32種類の選び方がある
  • それを無駄なく列挙する方法は蟻本に書いてある
    ll sup = 0b01101101;
    ll sub = sup;
    do{
      debug(bitset<10>(sub));
      sub = (sub-1)&sup;
    }while(sub!=sup);

実行結果

[bitset<10>(sub)]: 1011011000
[bitset<10>(sub)]: 0011011000
[bitset<10>(sub)]: 1001011000
[bitset<10>(sub)]: 0001011000
[bitset<10>(sub)]: 1010011000
[bitset<10>(sub)]: 0010011000
[bitset<10>(sub)]: 1000011000
[bitset<10>(sub)]: 0000011000
[bitset<10>(sub)]: 1011001000
[bitset<10>(sub)]: 0011001000
[bitset<10>(sub)]: 1001001000
[bitset<10>(sub)]: 0001001000
[bitset<10>(sub)]: 1010001000
[bitset<10>(sub)]: 0010001000
[bitset<10>(sub)]: 1000001000
[bitset<10>(sub)]: 0000001000
[bitset<10>(sub)]: 1011010000
[bitset<10>(sub)]: 0011010000
[bitset<10>(sub)]: 1001010000
[bitset<10>(sub)]: 0001010000
[bitset<10>(sub)]: 1010010000
[bitset<10>(sub)]: 0010010000
[bitset<10>(sub)]: 1000010000
[bitset<10>(sub)]: 0000010000
[bitset<10>(sub)]: 1011000000
[bitset<10>(sub)]: 0011000000
[bitset<10>(sub)]: 1001000000
[bitset<10>(sub)]: 0001000000
[bitset<10>(sub)]: 1010000000
[bitset<10>(sub)]: 0010000000
[bitset<10>(sub)]: 1000000000
[bitset<10>(sub)]: 0000000000