組み合わせの生成は拙作のページ「順列と組み合わせ」で説明しました。このほかに、n 個の中から m 個を選ぶ組み合わせは、ビットのオンオフで表すことができます。たとえば、5 個の数字 (0 - 4) から 3 個を選ぶ場合、数字を 0 bit から 4 bit に対応させます。すると、1, 3, 4 という組み合わせは 11010 と表すことができます。今回はビットを使って組み合わせを求めてみましょう。最初に OCaml のビット演算について説明します。
OCaml にはビット演算を行う演算子が用意されています。主な演算子を表に示します。
| 演算子 | 型 | 機能 |
|---|---|---|
| land | int -> int -> int | ビットごとの論理積を返す |
| lor | int -> int -> int | ビットごとの論理和を返す |
| lxor | int -> int -> int | ビットごとの排他的論理和を返す |
| lnot | int -> int | ビットごとの論理的な否定を返す |
| lsl | int -> int -> int | m lsl n は m を n ビットだけ左シフトする |
| lsr | int -> int -> int | m lsr n は m を n ビットだけ右シフトする |
| asr | int -> int -> int | m lsr n は m を n ビットだけ算術右シフトする |
land はビットごとの論理積を返します。
# 5 land 3;; - : int = 1
0101
and 0011
---------
0001
lor はビットごとの論理和を返します。
# 5 lor 3;; - : int = 7
0101
or 0011
--------
0111
lxor はビットごとの排他的論理和を返します。
# 5 lxor 3;; - : int = 6
0101
xor 0011
---------
0110
lnot はビットごとの論理的な否定を返します。
# lnot 0;; - : int = -1 # lnot 1;; - : int = -2
m lsl n は m を n ビット左シフトします。m lsr n は m を n ビット右シフトします。
# 1 lsl 8;; - : int = 256 # 256 lsr 4;; - : int = 16
このほかに、算術右シフトを行う演算子 asr もあります。
組み合わせを求めるプログラムは次のようになります。
リスト 4 : 組み合わせの生成
let rec combination n m a =
if m = 0 then Printf.printf "%x\n" a
else if m = n then Printf.printf "%x\n" (a lor ((1 lsl m) - 1))
else begin
combination (n - 1) m a;
combination (n - 1) (m - 1) (a lor (1 lsl (n - 1)))
end
関数 combination は n 個の中から m 個を選ぶ組み合わせを生成して出力します。組み合わせは引数 a にセットします。m が 0 になったら、組み合わせがひとつできたので a を出力します。n が m と等しくなったならば、残り m 個を全て選びます。(1 lsl m) - 1 で m 個のビットをオンにして出力します。
あとは combination を再帰呼び出しします。最初の呼び出しは n 番目の数字を選ばない場合です。n - 1 個の中から m 個を選びます。次の呼び出しが n 番目の数字を選ぶ場合で、a の n - 1 ビットをオンにします。そして、n - 1 個の中から m - 1 個を選びます。
それでは 5 個の中から 3 個を選ぶ combination 5 3 0 の実行例を示します。
7 (00111) b (01011) d (01101) e (01110) 13 (10011) 15 (10101) 16 (10110) 19 (11001) 1a (11010) 1c (11100)
この場合、最小値は 0x07 (00111) で最大値は 0x1c (11100) になります。このように、combination は組み合わせを表す数を昇順で出力します。
次は、N 通りある組み合わせに 0 から N - 1 までの番号を付ける方法を紹介しましょう。たとえば、6 個の中から 3 個を選ぶ組み合わせは 20 通りありますが、この組み合わせに 0 から 19 までの番号を付けることができます。1 1 1 0 0 0 を例題に考えてみましょう。次の図を見てください。
5 4 3 2 1 0
─────────
0 0 0 1 1 1 ↑
0 0 1 0 1 1 │
0 0 1 1 0 1 │
0 0 1 1 1 0 │
0 1 0 0 1 1 │
0 1 0 1 0 1 5Ｃ3 = 10 通り
0 1 0 1 1 0 │
0 1 1 0 0 1 │
0 1 1 0 1 0 │
0 1 1 1 0 0 ↓
─────────
1 0 0 0 1 1 ↑
1 0 0 1 0 1 │
1 0 0 1 1 0 │
1 0 1 0 0 1 4Ｃ2 = 6 通り
1 0 1 0 1 0 │
1 0 1 1 0 0 ↓
────────
1 1 0 0 0 1 ↑
1 1 0 0 1 0 3Ｃ1 = 3 通り
1 1 0 1 0 0 ↓
───────
1 1 1 0 0 0 19 番目
─────────
図 : 6Ｃ3 の組み合わせ
最初に 5 をチェックします。5 を選ばない場合は \({}_5 \mathrm{C}_3\) = 10 通りありますね。この組み合わせに 0 から 9 までの番号を割り当てることにすると、5 を選ぶ組み合わせの番号は 10 から 19 までとなります。
次に、4 をチェックします。4 を選ばない場合は、\({}_4 \mathrm{C}_2\) = 6 通りあります。したがって、5 を選んで 4 を選ばない組み合わせに 10 から 15 までの番号を割り当てることにすると、5 と 4 を選ぶ組み合わせには 16 から 19 までの番号となります。
最後に、3 をチェックします。同様に 3 を選ばない場合は 3 通りあるので、これに 16 から 18 までの番号を割り当て、5, 4, 3 を選ぶ組み合わせには 19 を割り当てます。これで組み合わせ 1 1 1 0 0 0 の番号を求めることができました。
では、0 0 0 1 1 1 はどうなるのでしょうか。左から順番にチェックしていくと、最初の 1 が見つかった時点で、その数字を選ばない組み合わせは存在しません。つまり、残りの数字をすべて選ぶしかないわけです。したがって、これが 0 番目となります。
このように、数字を選ぶときに、数字を選ばない場合の組み合わせの数を足し算していけば、その組み合わせの番号を求めることができるのです。
組み合わせを番号に変換するプログラムは次のようになります。
リスト 5 : 組み合わせを番号に変換
(* 組み合わせの数を求める *)
let rec comb n r =
if n = r || r = 0 then 1
else (comb n (r - 1)) * (n - r + 1) / r
(* 組み合わせを番号に変換 *)
let rec comb_to_num c n r v =
if r = 0 || n = r then v
else if c land (1 lsl (n - 1)) <> 0 then
comb_to_num c (n - 1) (r - 1) (v + comb (n - 1) r)
else
comb_to_num c (n - 1) r v
関数 comb_to_num の引数 c はビットのオンオフで表した組み合わせ、引数 n と r は nＣr の n と r を表しています。引数 v は求める番号を表します。n と r の値が同じになるか、もしくは r が 0 になれば、組み合わせの番号を計算できたので value を返します。
そうでない場合、c の n - 1 ビットの値を調べます。ビットがオンであれば、v に comb (n - 1) r の値を足し算し、r を -1 して comb_to_num を再帰呼び出しします。そうでなければ、v と r の値はそのままで comb_to_num を再帰呼び出しします。
逆に、番号から組み合わせを求めるプログラムも簡単に作ることができます。次のリストを見てください。
リスト 6 : 番号を組み合わせに変換
let rec num_to_comb v n r c =
if r = 0 then c
else if n = r then c lor ((1 lsl n) - 1)
else
let k = comb (n - 1) r in
if v >= k then
num_to_comb (v - k) (n - 1) (r - 1) (c lor (1 lsl (n - 1)))
else
num_to_comb v (n - 1) r c
引数 v が番号で、引数 n と r は \({}_n \mathrm{C}_r\) の n と r を表しています。引数 c が求める組み合わせです。たとえば、n = 5, r = 3 の場合、ビットが 1 になるのは \({}_4 \mathrm{C}_2\) = 6 通りあり、0 になるのは \({}_4 \mathrm{C}_3\) = 4 通りあります。したがって、数値が 0 - 3 の場合はビットを 0 にし、4 - 9 の場合はビットを 1 にすればいいわけです。
ビットを 0 にした場合、残りは \({}_4 \mathrm{C}_3\) = 4 通りになるので、同様に次のビットを決定します。ビット 1 にした場合、残りは \({}_4 \mathrm{C}_2\) = 6 通りになるので、v から 4 を引いて num_to_comb を再帰呼び出しして次のビットを決定します。
r が 0 の場合は、組み合わせが完成したので c を返します。n と r が等しい場合は、残りのビットをすべて 1 にセットしてから c を返します。それ以外の場合は、\({}_{n-1} \mathrm{C}_r\) の値を comb (n - 1) r で求めて変数 k にセットします。v が k 以上であれば変数 c のビットを 1 にセットし、v から k を引き算して comb_to_num を再帰呼び出しします。そうでなければ、num_to_comb を再帰呼び出しするだけです。
それでは、n = 5, r = 3 の場合の実行例を示します。
# for i = 0 to 9 do
let v = num_to_comb i 5 3 0 in
let n = comb_to_num v 5 3 0 in
Printf.printf "%d => %x => %d\n" i v n
done;;
0 => 7 => 0
1 => b => 1
2 => d => 2
3 => e => 3
4 => 13 => 4
5 => 15 => 5
6 => 16 => 6
7 => 19 => 7
8 => 1a => 8
9 => 1c => 9
正常に動作していますね。この方法を使うと、n 個ある組み合わせの中の i 番目 (0 <= i < n) の組み合わせを簡単に求めることができます。
最も右側 (LSB 側) にある 1 を 0 にクリアする、逆に最も右側にある 0 を 1 にセットすることは簡単にできます。
(1) 右側にある 1 をクリア => x AND (- x) x : 1 1 1 1 x - 1 : 1 1 1 0 ---------------- AND : 1 1 1 0 x : 1 0 0 0 x - 1 : 0 1 1 1 ---------------- AND : 0 0 0 0 (2) 右側にある 0 を 1 にセット => x OR (x + 1) x : 0 0 0 0 x + 1 : 0 0 0 1 ---------------- OR : 0 0 0 1 x : 0 1 1 1 x + 1 : 1 0 0 0 ---------------- OR : 1 1 1 1
上図 (1) を見てください。x から 1 を引くと、右側から連続している 0 は桁借りにより 1 になり、最初に出現する 1 が 0 になります。したがって、x AND (x - 1) を計算すると、最も右側にある 1 を 0 にクリアすることができます。(2) の場合、x に 1 を足すと、右側から連続している 1 は桁上がりにより 0 になり、最初に出現する 0 が 1 になります。x OR (x + 1) を計算すれば、最も右側にある 0 を 1 にセットすることができます。
また、最も右側にある 1 を取り出すことも簡単にできます。簡単な例として 4 ビットの整数値を考えてみます。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。
0 : 0000
1 : 0001 -1 : 1111 1 AND (-1) => 0001
2 : 0010 -2 : 1110 2 AND (-2) => 0010
3 : 0011 -3 : 1101 3 AND (-3) => 0001
4 : 0100 -4 : 1100 4 AND (-4) => 0100
5 : 0101 -5 : 1011 5 AND (-5) => 0001
6 : 0110 -6 : 1010 6 AND (-6) => 0010
7 : 0111 -7 : 1001 7 AND (-7) => 0001
-8 : 1000
図 : 最も右側にある 1 を取り出す方法
2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。したがって、x と -x の論理積 x AND (-x) は、最も右側にある 1 だけが残り、あとのビットはすべて 0 になります。
次は、ビットが 1 の個数を数える処理を作ってみましょう。次のリストを見てください。
リスト : ビットカウント
let bit_count n =
let rec _bit_count n c =
if n = 0 then c
else _bit_count (n land (n - 1)) (c + 1)
in _bit_count n 0
整数 n の右側から順番に 1 をクリアしていき、0 になるまでの回数を求めます。とても簡単ですね。
整数を 32 bit に限定する場合、次の方法で 1 の個数をもっと高速に求めることができます。
リスト : ビットカウント (2) let bit_count32 n = let a = (n land 0x55555555) + ((n lsr 1) land 0x55555555) in let b = (a land 0x33333333) + ((a lsr 2) land 0x33333333) in let c = (b land 0x0f0f0f0f) + ((b lsr 4) land 0x0f0f0f0f) in let d = (c land 0x00ff00ff) + ((c lsr 8) land 0x00ff00ff) in (d land 0xffff) + (d lsr 16)
最初に、整数を 2 bit ずつに分割して 1 の個数を求めます。たとえば、整数 n を 4 bit で考えてみましょう。5 を 2 進数で表すと 0101 になります。n と論理積を計算すると 0, 2 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。同様に n を 1 ビット右シフトして論理積を計算すると、1, 3 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。あとは、それを足し算すれば 2 bit の中にある 1 の個数を求めることができます。
変数 a には 2 ビットの中の 1 の個数が格納されています。左隣の 2 ビットの値を足し算すれば、4 ビットの中の 1 の個数を求めることができます。次に、左隣の 4 ビットの値を足し算して 8 ビットの中の 1 の個数を求め、左隣の 8 ビットの値を足し算して、というように順番に値を加算していくと 32 ビットの中にある 1 の個数を求めることができます。
bit_count は 1 の個数が多くなると遅くなりますが、bit_count32 は 1 の個数に関係なく高速に動作します。興味のある方は試してみてください。