python bit full search

>>> from itertools import product
>>> n = 3
>>> [[i for i, j in zip(range(n), mask) if j] for mask in product((0, 1), repeat=n)]
[[], [2], [1], [1, 2], [0], [0, 2], [0, 1], [0, 1, 2]]

>>> n = 5
>>> [[i for i, j in zip(range(n), mask) if j] for mask in product((0, 1), repeat=n)]
[[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 3, 4], [0], [0, 4], [0, 3], [0, 3, 4], [0, 2], [0, 2, 4], [0, 2, 3], [0, 2, 3, 4], [0, 1], [0, 1, 4], [0, 1, 3], [0, 1, 3, 4], [0, 1, 2], [0, 1, 2, 4], [0, 1, 2, 3], [0, 1, 2, 3, 4]]

>>> n = 3
>>> [[i for i in range(bit) if bit & (1<<i)] for bit in range(1<<n)]
[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]

>>> n = 5
>>> [[i for i in range(bit) if bit & (1<<i)] for bit in range(1<<n)]
[[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2], [3], [0, 3], [1, 3], [0, 1, 3], [2, 3], [0, 2, 3], [1, 2, 3], [0, 1, 2, 3], [4], [0, 4], [1, 4], [0, 1, 4], [2, 4], [0, 2, 4], [1, 2, 4], [0, 1, 2, 4], [3, 4], [0, 3, 4], [1, 3, 4], [0, 1, 3, 4], [2, 3, 4], [0, 2, 3, 4], [1, 2, 3, 4], [0, 1, 2, 3, 4]]

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int N = 3;

  map<int, vector<int>> mp;
  rep(bit, (1 << N)) rep(i, bit) if (bit & (1 << i)) mp[bit].push_back(i);

  for (auto x : mp) {
    cout << x.first << " : ";
    for (int n : x.second) cout << n << ' ';
    cout << endl;
  }
}

1 : 0 
2 : 1 
3 : 0 1 
4 : 2 
5 : 0 2 
6 : 1 2 
7 : 0 1 2 

Recommended Posts