n個からk個取る組み合わせを全探索したいときメモ

bit全探索に慣れたい。

蟻本より、n個からk個取る組み合わせのJava版

public class Main {
    public static void main(String[] args){
        int n = 4;
        int k = 2;
        
        int comb = (1<<k) -1;
        while(comb < 1 << n){
            System.out.println(Integer.toString(comb,2));
            int x = comb & -comb;
            int y = comb + x;
            comb = ( (comb & ~y) / x >> 1 ) | y;
        }
    }
}
/*
11
101
110
1001
1010
1100
*/

式の意味がわからなかったから行間を埋める。

• 0でない整数xに対して、x & -xは最下位の1のビットのみを取り出す
  • -xは補数の定義より~x + 1
  • ~xはxの最下位に続く0たちがすべて1になっている数だから、そこに1を足すと求めたいビットだけxと~x+1に対して1が揃うイメージ。
  • 補数の定義は足すと繰り上がりになる数のうち最小の数
• x = comb & -combとすると、y = comb + xはcombの末尾にある...001111000を...010000000にしてくれる
• 上の例で言うとyはビットを3つ失っている。どこかで3つ分補充したい。comb & ~yを考えると元々並んでいた末尾の1のグループ(4つ並んだ1)だけ得ることができる。xは末尾の1のグループの最下位であるため、xで割ってあげれば4つの1を得ることができる。さらに1ビット右にシフトすれば、(4-1=)3個の1を手に入れることができる。((comb & ~y) / x >> 1)
• 上で手に入れたものが補充したいビットである。( (comb & ~y) / x >> 1 ) | y

隣り合う要素を同時に含まないような集合についてはまた今度考えよう。