bit演算でやる組み合わせ列挙の咀嚼

アルゴリズム探し

突然誰かに「5つのものの中から3つ選ぶ際の組み合わせを全て列挙して！」って言われた時のためにちょっと備えておきたいですね。(キリッ)

「組み合わせ列挙」自体の説明はまぁいいとして、それをプログラムでどう記述するかって考えると悩んじゃいますね。自分で考えたプログラムを見ると、ループを余計に多く回しちゃってるんじゃないかって気持ちになります。

そこで、なにかスマートなやり方がないか調べてみると以下の記事が見つかりました。

qiita.com

こちらの記事の「next_combination」というのがそれにあたります。

自分は理解するスピードが遅いので、この処理を見たときはしばらくチンプンカンプンでした。（笑）

ですが、考えてくうちに「こういうことなんじゃないか」とまとまってきたので、それを書いておこうと思います。

考え方を想像する

例えば、2進数で考えて辞書的に001101の次の組み合わせは何になるでしょうか。

正解は001110ですが、このとき何を考えたのか自分の思考を振り返ってみます。

「次の組み合わせ」というのは、組み合わせを数として見た時に「今より大きい数の中で一番小さい数」と考えられます。 今の数をちょっと大きくするので、直感的に下位の方にある1を並べ替えればよさそうです。

ここで以下2つの場合について考えます。
下位から見ていって最初に登場するのが..

1. 「..01の場合」（1が孤立）
   　例：01101, 11001, 11010

2. 「..11の場合」（1が連続）
   　例：00111, 01110, 10110,

です。

全ての組み合わせは必ず上記2つの場合のどちらかに分けられます。 では、それぞれの場合について見ていきます。

1. ..01の場合（1が孤立）

下位の方にある1を並べ替えて「今より大きい数の中で一番小さい数」を作れるかを見ていくことになるので、

「1bit目までを並べ替えてより大きくできるか」
「2bit目までを並べ替えてより大きくできるか」
　...
「N bit目までを並べ替えてより大きくできるか」

といったように、右から1bitずつ見る範囲を広げて調べていきます。
するといつか、N bit目で「より大きい数」を作ることができます。

11010を例にすると以下のようになります。

結論、..01の場合は最初の1を左に1つ詰めればいいです。

1を左に詰めたことで「より大きい数」という条件を満たしました。次は「その中で一番小さい数」という条件を満たさないといけないのですが、もう動かせる1はなく並べ替えた下位3bit（100）はこれ以上小さくすることができないので、11100が次の組み合わせになります。

2. ..11の場合（1が連続）

こちらも..01の場合と似ていますが、多少操作が異なります。

10110を例にすると以下のようになります。

結論、..11の場合は連続の最後の1を左に1つ詰め、残りの1を全て右端まで詰めればいいです。

連続の最後の1を左に詰めたことで「より大きい数」という条件を満たしました。そして、残りの1を右端に詰めたことで「その中で一番小さい数」という条件を満たしました。よって、11001が次の組み合わせになります。

bit演算の気持ち

では、bit演算でどうやっているのかを見ていきます。
以下はRustで書いてみたものです。
（変数名がイケてないかもですが、ご了承ください。笑）

fn next_combination(sub: i8) -> i8 {
    let least = sub & -sub;
    let left = sub + least;
    let right = ((sub & !left) / least) >> 1;
    left | right
}

GitHub - nemutage/bitwise-next-combination: Implementation of next-combination using bitwise operations

「5つのものの中から3つ選ぶ際の組み合わせ」は以下のように出力されます。

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

では各演算の意図を交えつつ、subが11010の場合と10110場合の両方を見ていきます。

より大きい数

let least = sub & -sub;
let left = sub + least;

まず、一番右の1を取り出します。（least）
それを元の数に足して繰り上げることで「1を左に詰めて」います。（left）
これで「より大きい数」という条件を満たしました。

変数・演算	値
sub	11010
least	00010
left	11100

変数・演算	値
sub	10110
least	00010
left	11000

その中で一番小さい数

let right = ((sub & !left) / least) >> 1;
left | right

「より大きい数」という条件を満たす要素である左半分は確定しました。（left）
今度を右半分を操作するために取り出します。（sub & !left）
そして1を「右端に詰めて」います。（(sub & !left) / least）
この時点でまだ「左に詰めた」はずの1が残っているので、それを除去します。（right）
これで「その中で一番小さい数」という条件を満たしました。

最後に、「より大きい数」を満たすための要素と「その中で一番小さい数」を満たすための要素を合わせてこれを次の組み合わせとします。（left | right）

変数・演算	値
sub	11010
least	00010
left	11100
sub & !left	00010
(sub & !left) / least	00001
right	00000
left | right	11100

変数・演算	値
sub	10110
least	00010
left	11000
sub & !left	00110
(sub & !left) / least	00011
right	00001
left | right	11001

まとめ

bit演算でやる組み合わせ列挙を自分なりに噛み砕いてみました。
こんなのが思いつくなんてすごいですね。
自分でも思いつきたいものです。

参考文献

ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 - Qiita