bit演算でやる組み合わせ列挙の咀嚼
アルゴリズム探し
突然誰かに「5つのものの中から3つ選ぶ際の組み合わせを全て列挙して!」って言われた時のためにちょっと備えておきたいですね。(キリッ)
「組み合わせ列挙」自体の説明はまぁいいとして、それをプログラムでどう記述するかって考えると悩んじゃいますね。自分で考えたプログラムを見ると、ループを余計に多く回しちゃってるんじゃないかって気持ちになります。
そこで、なにかスマートなやり方がないか調べてみると以下の記事が見つかりました。
こちらの記事の「next_combination」というのがそれにあたります。
自分は理解するスピードが遅いので、この処理を見たときはしばらくチンプンカンプンでした。(笑)
ですが、考えてくうちに「こういうことなんじゃないか」とまとまってきたので、それを書いておこうと思います。
考え方を想像する
例えば、2進数で考えて辞書的に001101
の次の組み合わせは何になるでしょうか。
正解は001110
ですが、このとき何を考えたのか自分の思考を振り返ってみます。
「次の組み合わせ」というのは、組み合わせを数として見た時に「今より大きい数の中で一番小さい数」と考えられます。
今の数をちょっと大きくするので、直感的に下位の方にある1
を並べ替えればよさそうです。
ここで以下2つの場合について考えます。
下位から見ていって最初に登場するのが..
「
..01
の場合」(1
が孤立)
例:01101
,11001
,11010
「
..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 }
「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演算でやる組み合わせ列挙を自分なりに噛み砕いてみました。
こんなのが思いつくなんてすごいですね。
自分でも思いつきたいものです。