SML/NJ や Lisp などの関数型言語では、データ構造を表すのにリストがよく使われます。ところが、問題によってはリストよりもビットで表した方が、プログラムを作るのに都合がよい場合もあります。
SML/NJ の場合、整数の論理演算とビット操作はデータ型 int で行うことはできません。SML/NJ には「無符号整数 (unsigned integer) 」を表すデータ型 word が用意されていて、論理演算とビット操作は word を使って行います。次の例を見てください。
- Word.wordSize; val it = 31 : int - val a = 0w256; val a = 0wx100 : word - val b = 0w512; val b = 0wx200 : word - a + b; val it = 0wx300 : word - 0wx7fffffff + 0w1; val it = 0wx0 : word
word の最大値 (ビット数) は変数 wordSize に定義されています。Windows 版 SML/NJ の場合、wordSize は 31 なので、word の範囲は 0 から 2147483647 (0x7ffffff) までになります。word は数値の前に 0w を付けて表します。0w の後ろに x を付けると 16 進数になります。対話モードの場合、word は 16 進数で表示されます。なお、算術演算子 (+, -, *, div) や比較演算子 (=, <>, <, >, <=, >=) は、int と同様に word でも使うことができます。ただし、最後の例のようにオーバーフローしても例外は送出されません。ご注意ください。
ストラクチャ Word には word を操作する関数が定義されています。論理演算とビット操作を行う主な関数を表に示します。
| 関数名 | 機能 |
|---|---|
| andb : word * word -> word | ビットごとの論理積を返す |
| orb : word * word -> word | ビットごとの論理和を返す |
| xorb : word * word -> word | ビットごとの排他的論理和を返す |
| notb : word -> word | ビットごとの論理的な否定を返す |
| >> : word * word -> word | >>(w, n) は w を n ビットだけ右シフトする |
| << : word * word -> word | <<(w, n) は w を n ビットだけ左シフトする |
andb はビットごとの論理積を返します。
- Word.andb( 0w5, 0w3 ); val it = 0wx1 : word
0101
and 0011
---------
0001
orb はビットごとの論理和を返します。
- Word.orb( 0w5, 0w3 ); val it = 0wx7 : word
0101
or 0011
--------
0111
xorb はビットごとの排他的論理和を返します。
- Word.xorb( 0w5, 0w3 ); val it = 0wx6 : word
0101
xor 0011
---------
0110
notb はビットごとの論理的な否定を返します。
- Word.notb( 0w0 ); val it = 0wx7fffffff : word - Word.notb( 0wx7ffffffe ); val it = 0wx1 : word
<<( w, n ) は w を n ビット左シフトします。>>( w, n ) は w を n ビット右シフトします。
- Word.<<( 0w1, 0w8 ); val it = 0wx100 : word - Word.>>( 0wx100, 0w4 ); val it = 0wx10 : word
このほかに、算術右シフトを行う関数 ~>>( w, n ) もあります。
データを変換する場合は次の関数を使います。
val toInt : word -> int val fromInt : int -> word val toString : word -> string val fromString : string -> word option
簡単な例を示します。
- Word.fromInt( 10 ); val it = 0wxa : word - Word.toInt( 0wx100 ); val it = 256 : int - Word.toString( 0wxabcd ); val it = "abcd" : string - Word.fromString( "ABCD" ); val it = SOME 0wxabcd : word option - Word.fromString( "xyz" ); val it = NONE : word option
文字列を word に変換できない場合、fromString は NONE を返します。
Windows 版 SML/NJ の word は 31 bit 無符号整数ですが、このほかに 8 bit 無符号整数の Word8 と 32 bit 無符号整数の Word32 が用意されています。次の例を見てください。
- Word8.notb( 0w0 ); val it = 0wxff : Word8.word - Word31.notb( 0w0 ); val it = 0wx7fffffff : word - Word32.notb( 0w0 ); val it = 0wxffffffff : Word32.word
Windows 版 SML/NJ の場合、word は Word31 と同じになります。また、SML/NJ には LargeWord という無符号整数も用意されていますが、Windows 版では Word32 と同じになります。Word8 の範囲は 0 から 255 (0xff) まで、Word32 の範囲は 0 から 4294967295 (0xffffffff) になります。どちらも Word と同じ操作関数を使うことができます。
それでは簡単な例題として、組み合わせを生成するプログラムを作ってみましょう。組み合わせの生成は ちょっと寄り道「組み合わせの生成」 で説明しました。今回は n 個の中から r 個を選ぶ組み合わせをビットのオンオフで表すことにします。
たとえば、5 個の数字 (0 - 4) から 3 個を選ぶ場合、数字を 0 bit から 4 bit に対応させます。すると、1, 3, 4 という組み合わせは 11010 と表すことができます。これを SML/NJ でプログラムすると次のようになります。
リスト : 組み合わせの生成
(* n 個の中から r 個を選ぶ *)
fun combination( _, 0w0, comb ) = print( Word.toString( comb ) ^ "\n" )
| combination( n, r, comb ) =
if n = r
then print( Word.toString( Word.orb( comb, Word.<<( 0w1, r ) - 0w1 )) ^ "\n" )
else (
(* n 番目の要素を選ばない *)
combination( n - 0w1, r, comb );
(* n 番目の要素を選ぶ *)
combination( n - 0w1, r - 0w1, Word.orb( comb, Word.<<( 0w1, n - 0w1 )))
)
関数 combination は n 個の中から r 個を選ぶ組み合わせを生成して出力します。組み合わせは引数 comb にセットします。r が 0 になったら、組み合わせがひとつできたので comb を出力します。n が r と等しくなったならば、残り r 個を全て選びます。 0 から r - 1 番目のビットをオンにするため、2r - 1 と comb の論理和を計算します。プログラムでは 2r - 1 を <<( 0w1, r ) - 0w1 で計算しています。これで r 個のビットをオンにすることができます。
あとは combination を再帰呼び出しします。最初の呼び出しは n 番目の要素を選ばない場合です。n - 1 個の中から r 個を選びます。次の呼び出しが n 番目の要素を選ぶ場合です。0w1 を n - 1 ビット左シフトして comb と論理和を計算します。これで、n - 1 番目のビットをオンにすることができます。そして、n - 1 個の中から r - 1 個を選びます。
それでは 5 個の中から 3 個を選ぶ combination( 0w5, 0w3, 0w0 ) の実行例を示します。
7 (00111) b (01011) d (01101) e (01110) 13 (10011) 15 (10101) 16 (10110) 19 (11001) 1a (11010) 1c (11100)
この場合、最小値は 0wx07 (00111) で最大値は 0wx1c (11100) になります。このように、combination は組み合わせを表す数を昇順で出力します。ところで、参考文献 [1] の「組み合わせの生成」には、再帰呼び出しを使わずに同じ結果を得る方法が解説されてます。とても巧妙な方法なので、興味のある方は読んでみてください。
ところで、組み合わせを生成する combination は整数 (int) を使ってもプログラムすることができます。次のリストを見てください。
リスト：組み合わせの生成（整数版）
fun pow2( 0 ) = 1
| pow2( n ) = 2 * pow2( n - 1 )
fun combination( _, 0, comb ) = print( Int.toString( comb ) ^ "\n" )
| combination( n, r, comb ) =
if n = r
then print( Int.toString( comb + pow2( r ) - 1 ) ^ "\n" )
else (
combination( n - 1, r, comb );
combination( n - 1, r - 1, comb + pow2( n - 1 ) )
)
2n を求める関数 pow2 を用意します。すると、Word.<<( 0w1, r ) は pow2( r ) で、Word.orb は加算 ( + ) でプログラムすることができます。combination( 5, 3, 0 ) の実行例を示します。
7 11 13 14 19 21 22 25 26 28
結果は 10 進数で表示されていることに注意してください。
もう一つ簡単な例題として、Puzzel DE Programming で取り上げた ライツアウト というパズルを SML/NJ で解いてみましょう。なお、このドキュメントは拙作のページ Common Lisp 入門 整数の論理演算とビット操作 のプログラムを SML/NJ で書き直したものです。内容は重複していますが、ご了承くださいませ。
ライツアウトは光っているボタンをすべて消すことが目的のパズルです。ルールはとても簡単です。あるボタンを押すと、そのボタンと上下左右のボタンの状態が反転します。つまり、光っているボタンは消灯し消えていたボタンは点灯します。次の図を見てください。
□□□□□ □□□□□ ０ １ ２ ３ ４
□□□□□ □□■□□ ５ ６ ７ ８ ９
□□□□□ ─→ □■■■□ 10 11 12 13 14
□□□□□ □□■□□ 15 16 17 18 19
□□□□□ □□□□□ 20 21 22 23 24
（Ａ）中央のボタンを押した場合 （Ｂ）座標
図 : ライツアウトの点灯パターン
ボタンは 5 行 5 列に配置されています。上図に示したように、中央のボタン 12 を押すとそのボタンと上下左右のボタンの状態が反転します。
ライツアウトはライトオン・オフの 2 種類の状態しかないので、盤面はリストよりもビットを使って表した方が簡単です。ライトオン・オフの状態を 1 と 0 で表し、各ビットとボタンの座標を対応させると、盤面は 0 から 33554431 の整数値で表すことができます。
ボタンを押してライトの状態を反転する処理も簡単です。たとえば、中央のボタン 12 を押した場合、7, 11, 12, 13, 17 のライトを反転させます。この場合、5 つのボタンのビットをオンにした値 0wx23880 と、盤面を表す整数値の排他的論理和 (xor) を求めれば、5 つのライトの状態を反転することができます。次の例を見てください。
0w0 xor 0wx23880 => 0wx23880 (* 消灯の状態でボタン 12 を押す（点灯する）*) 0wx23880 xor 0wx23880 => 0w0 (* もう一度同じボタンを押す（消灯する）*)
このように、ライツアウトは同じボタンを二度押すと元の状態に戻ります。したがって、同じボタンは二度押さなくてよいことがわかります。また、実際にボタンを押してみるとわかりますが、ボタンを押す順番は関係がないことがわかります。たとえば、ボタン 0 と 1 を押す場合、0 -> 1 と押すのも 1 -> 0 と押すのも同じ結果になります。
この 2 つの法則から、ボタンを押す組み合わせは全部で 225 通りになります。ライツアウトを解くいちばん単純な方法は、ボタンを押す組み合わせを生成して、実際にライトが全部消えるかチェックすることです。ところが、この方法ではちょっと時間がかかるのです。高速 CPU を搭載した最新マシンを使えば、それほど時間はかからないと思いますが、M.Hiroi のオンボロマシン (Windows 95, Pentium 166 MHz) ではけっこう時間がかかるでしょう。実はもっと高速に解く方法があるのです。
ライツアウトは次の図に示すように、ボタンを上から 1 行ずつ消灯していくという、わかりやすい方法で解くことができます。
ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ
１□■□■□ １□□□□□ １□□□□□ １□□□□□
２□□□□□ ２■■□■■ ２□□□□□ ２□□□□□
３□□□□□ ３□■□■□ ３□■□■□ ３□□□□□
４□□□□□ ４□□□□□ ４■■□■■ ４□□□□□
５□□□□□ ５□□□□□ ５□□□□□ ５□■□■□
（１） （２） （３） （４）
図 : 1 行ずつボタンを消灯していく方法
(1) では、1 行目のボタンが 2 つ点灯しています。このボタンを消すには、真下にある 2 行目の B と D のボタンを押せばいいですね。すると (2) の状態になります。次に、2 行目のボタンを消します。3 行目の A, B, D, E のボタンを押して (3) の状態になります。
あとはこれを繰り返して 4 行目までのボタンを消したときに、5 行目のボタンも全部消えていれば成功となります。(4) のように、5 行目のボタンが消えない場合は失敗です。この場合は、1 行目のボタンを押して、点灯パターンを変更します。
2 - 5 行目のボタンの押し方は、1 行目の点灯パターンにより決定されるので、けっきょく 1 行目のボタンの押し方により、解けるか否かが決まります。この場合、ボタンの押し方は、25 = 32 通りしかありせん。つまり、たった 32 通り調べるだけでライツアウトの解を求めることができるのです。
このほかに、高橋謙一郎さんの コンピュータ＆パズル では、細江万太郎さんが考案されたライツアウトを連立方程式で解く方法が紹介されています。この方法には M.Hiroi も驚きました。
それではプログラムを作りましょう。次のリストをみてください。
リスト : ライツアウトの解法
(* ボタンを押したときのパターン *)
val pattern = #[0wx0000023, 0wx0000047, 0wx000008e, 0wx000011c, 0wx0000218,
0wx0000461, 0wx00008e2, 0wx00011c4, 0wx0002388, 0wx0004310,
0wx0008c20, 0wx0011c40, 0wx0023880, 0wx0047100, 0wx0086200,
0wx0118400, 0wx0238800, 0wx0471000, 0wx08e2000, 0wx10c4000,
0wx0308000, 0wx0710000, 0wx0e20000, 0wx1c40000, 0wx1880000]
(* 解を求める *)
fun solve( 32, _ ) = ()
| solve( n, board ) =
let
val pat1 = Word.fromInt( n )
val board1 = push_button_1( 0, pat1, board )
val (board2, pat2) = light_off( 0, pat1, board1 )
in
if board2 = 0w0 then print_answer( 0, pat2 ) else ();
solve( n + 1, board )
end
最初に、ボタンを押したときにライトの状態を反転させるための値をベクタ pattern に定義します。そして、関数 solve で盤面 board の解を求めます。
1 行目のボタンの押し方は 32 通りあるので、ボタンの押し方を 0 から 31 までの数値で表すことにします。これらの値は 5 ビットで表すことができるので、ビットとボタンの位置を対応させて、ビットがオンであればそのボタンを押すことにします。この処理を関数 push_button_1 で行います。
次に、関数 light_off で 1 行ずつライトを消していきます。light_off は新しい盤面 board2 と押したボタンをビットで表した値 pat2 を返します。board2 が 0w0 ならば、全部のライトが消灯しています。print_answer で押したボタンを表示します。そして、solve を再帰呼び出しして、次の解を探索します。
1 行目のボタンを押す関数 push_button_1 は次のようになります。
リスト : 1 行目のボタンを押す
(* ビットのチェック *)
fun check_bit( n, i ) =
Word.andb( n, Word.<<( 0w1, Word.fromInt( i ) ) ) <> 0w0
(* ビットのセット *)
fun set_bit( n, i ) = Word.orb( n, Word.<<( 0w1, Word.fromInt( i ) ) )
(* ボタンを押す *)
fun push_button( board, i ) = Word.xorb( board, Vector.sub( pattern, i ) )
(* 1 行目のボタンを押す *)
fun push_button_1( 5, pat, board ) = board
| push_button_1( i, pat, board ) =
if check_bit( pat, i )
then push_button_1( i + 1, pat, push_button( board, i ) )
else push_button_1( i + 1, pat, board )
関数 check_bit は word 型データ n の i 番目のビットが 1 であれば true を返し、0 であれば false を返します。関数 set_bit は word 型データ n の i 番目のビットを 1 にセットしたデータを返します。関数 push_button は盤面が board の状態で、i 番目のボタンを押してできる新しい盤面を返します。これは pattern の i 番目の要素と board の排他的論理和 (xor) を求めるだけです。
関数 push_button_1 は引数 pat の 0 から 4 番目のビットを check_bit で調べ、ビットが 1 であれば push_button で新しい盤面を作ります。ビットが 0 であればボタンを押しません。あとは、push_button_1 を再帰呼び出しして、次のビットをチェックします。第 1 引数が 5 になったならば、0 から 4 番目のビットを全部チェックしたので盤面 board を返します。
次は 1 行ずつライトを消していく関数 light_off を作ります。次のリストを見てください。
リスト : ライトを消す
fun light_off( 20, pat, board ) = (board, pat)
| light_off( n, pat, board ) =
if check_bit( board, n )
then light_off( n + 1, set_bit( pat, n + 5 ), push_button( board, n + 5 ) )
else light_off( n + 1, pat, board )
light_off は 0 から 20 番目のライトをチェックし、点灯しているならば 1 段下のボタンを押してライトを消灯します。第 1 引数の n がチェックするライトの位置、第 2 引数 pat は押したボタンを表す word 型データ、第 3 引数 board が盤面です。第 1 引数が 20 になったら処理が終了したので (board, pat) を返します。
次に、check_bit でライトが点灯しているか調べます。そうであれば、push_button で 1 行下のボタン (n + 5) を押し、set_bit で pat の (n + 5) 番目のビットを 1 にして、light_off を再帰呼び出しします。ライトが消えていれば、何もせずに light_off を再帰呼び出しします。
最後に、手順を表示する print_answer を作ります。
リスト : 手順の表示
(* ビットを求める *)
fun get_bit( n, i ) = Word.andb( 0w1, Word.>>( n, Word.fromInt( i ) ) )
(* 手順の表示 *)
fun print_answer( 25, push_pattern ) = print("\n")
| print_answer( n, push_pattern ) = (
if n mod 5 = 0 then print("\n") else ();
print( Word.toString( get_bit( push_pattern, n ) ) ^ " " );
print_answer( n + 1, push_pattern )
)
関数 get_bit は word 型データ n の i 番目のビットを求め、1 ならば 0w1 を返し、0 ならば 0w0 を返します。これは n を i ビット右シフトして、0w1 と論理積を計算するだけです。print_answer は押すボタンを 1 で、押さないボタンを 0 で表示します。5 行 5 列で出力するため、n mod 5 が 0 であれば print で改行を出力します。あとは get_bit でビットを求めて print で表示するだけです。
これでプログラムは完成です。それでは実行してみましょう。ライトが全部点灯している状態 (0wx1ffffff) を解いてみます。
- solve( 0, 0wx1ffffff ); 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 val it = () : unit
4 通りの解が出力されました。ボタンを押した回数はどの解も 15 回になります。実は、これがライツアウトの最長手数なのです。ライツアウトの場合、ライトの点灯パターンは 225 = 33554432 通りありますが、実際に解が存在するパターンは、その 1 / 4 の 8388608 通りしかありません。その中で 15 回で解けるパターンは 7350 通りあり、そのうちの一つがライトが全部点灯しているパターンなのです。
ライツアウトの最長手数に興味のある方は、Puzzle DE Programming：ライツアウト の 最長手数を求める をお読みくださいませ。
(*
* lightout.sml : ライツアウトの解法
*
* Copyright (C) 2005 Makoto Hiroi
*)
(* ボタンを押したときのパターン *)
val pattern = #[0wx0000023, 0wx0000047, 0wx000008e, 0wx000011c, 0wx0000218,
0wx0000461, 0wx00008e2, 0wx00011c4, 0wx0002388, 0wx0004310,
0wx0008c20, 0wx0011c40, 0wx0023880, 0wx0047100, 0wx0086200,
0wx0118400, 0wx0238800, 0wx0471000, 0wx08e2000, 0wx10c4000,
0wx0308000, 0wx0710000, 0wx0e20000, 0wx1c40000, 0wx1880000]
(* ビットのチェック *)
fun check_bit( n, i ) =
Word.andb( n, Word.<<( 0w1, Word.fromInt( i ) ) ) <> 0w0
(* ビットのセット *)
fun set_bit( n, i ) = Word.orb( n, Word.<<( 0w1, Word.fromInt( i ) ) )
(* ビットを求める *)
fun get_bit( n, i ) = Word.andb( 0w1, Word.>>( n, Word.fromInt( i ) ) )
(* ボタンを押す *)
fun push_button( board, i ) = Word.xorb( board, Vector.sub( pattern, i ) )
(* 1 行目のボタンを押す *)
fun push_button_1( 5, pat, board ) = board
| push_button_1( i, pat, board ) =
if check_bit( pat, i )
then push_button_1( i + 1, pat, push_button( board, i ) )
else push_button_1( i + 1, pat, board )
(* ライトを消す *)
fun light_off( 20, pat, board ) = (board, pat)
| light_off( n, pat, board ) =
if check_bit( board, n )
then light_off( n + 1, set_bit( pat, n + 5 ), push_button( board, n + 5 ) )
else light_off( n + 1, pat, board )
(* 手順の表示 *)
fun print_answer( 25, push_pattern ) = print("\n")
| print_answer( n, push_pattern ) = (
if n mod 5 = 0 then print("\n") else ();
print( Word.toString( get_bit( push_pattern, n ) ) ^ " " );
print_answer( n + 1, push_pattern )
)
(* 解を求める *)
fun solve( 32, _ ) = ()
| solve( n, board ) =
let
val pat1 = Word.fromInt( n )
val board1 = push_button_1( 0, pat1, board )
val (board2, pat2) = light_off( 0, pat1, board1 )
in
if board2 = 0w0 then print_answer( 0, pat2 ) else ();
solve( n + 1, board )
end
今回は nＣr 個の組み合わせに 0 から nＣr - 1 までの番号を付ける方法を紹介します。なお、組み合わせに番号を付ける方法は、拙作のページ Puzzle DE Programming の スライディングブロックパズル (1) で詳しく説明しています。内容は重複しますが、ご了承くださいませ。
たとえば、0 から 5 までの数字の中から 3 つ選ぶ組み合わせを考えてみましょう。この場合、組み合わせの総数は 6Ｃ3 = 20 通りになります。前回説明したように、各数字を 0 bit から 5 bit までに対応させると、2, 3, 4 という組み合わせは 0 1 1 1 0 0 と表すことができますね。したがって、組み合わせは 0 0 0 1 1 1 (7) から 1 1 1 0 0 0 (56) までになります。
今回はこの組み合わせに 0 から 19 までの番号を付ける方法です。たとえば、6Ｃ3 の組み合わせで 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Ｃ3 = 10 通りあります。この組み合わせに 0 から 9 までの番号を割り当てることにすると、5 を選ぶ組み合わせの番号は 10 から 19 までとなります。
次に、4 をチェックします。4 を選ばない場合は、4Ｃ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 番目となります。
このように、数字を選ぶときに、数字を選ばない場合の組み合わせの数を足し算していけば、その組み合わせの番号を求めることができるのです。プログラムは次のようになります。
リスト : 組み合わせに番号を付ける
(* 組み合わせの数 *)
fun ncr( n, r ) =
if n = r orelse r = 0 then 1
else ncr( n, r - 1 ) * (n - r + 1) div r
(* ビットチェック *)
fun check_bit( n, i ) =
Word.andb( n, Word.<<( 0w1, Word.fromInt( i ) ) ) <> 0w0
(* 組み合わせを番号に変換する *)
fun comb_to_num( n, r, comb ) =
let
fun toNum( n, r, value ) =
if n = r orelse r = 0 then value
else if check_bit( comb, n - 1 )
then toNum( n - 1, r - 1, value + ncr( n - 1, r ) )
else toNum( n - 1, r, value )
in
toNum( n, r, 0 )
end
関数 ncr は組み合わせの数 nＣr を求めます。関数 check_bit は、word 型データ n の i 番目のビットが 1 であれば ture を返し、0 であれば false を返します。関数 comb_to_num は n 個の中から r 個を選ぶ組み合わせ comb を番号に変換します。実際の処理は関数 toNum で行います。
toNum は comb の上位ビットから順番にチェックしていきます。n 個の中から r 個を選ぶ場合、n - 1 番目のビットが 1 であれば ncr( n - 1, r ) の値を value に加算して toNum を再帰呼び出しします。このとき、n 個の中から一つ選んだので、r の値を -1 することをお忘れなく。ビットが 0 であれば、value の値はそのままで toNum を再帰呼び出しします。n = r または r = 0 になったら value を返します。これが再帰呼び出しの停止条件になります。
次は、番号から組み合わせを求める関数 num_to_comb を作ります。次のリストを見てください。
リスト : 番号から組み合わせを求める
(* ビットセット *)
fun set_bit( n, i ) = Word.orb( n, Word.<<( 0w1, Word.fromInt( i ) ) )
(* 番号から組み合わせを求める *)
fun num_to_comb( n, r, value ) =
let
fun toComb( _, 0, _, comb ) = comb
| toComb( n, r, value, comb ) =
if n = r
then Word.orb( comb, Word.<<(0w1, Word.fromInt( n )) - 0w1 )
else
let
val k = ncr( n - 1, r )
in
if value >= k
then toComb( n - 1, r - 1, value - k, set_bit( comb, n - 1 ) )
else toComb( n - 1, r, value, comb )
end
in
toComb( n, r, value, 0w0 )
end
関数 set_bit は word 型データ n の i 番目のビットを 1 にセットしたデータを返します。関数 num_to_comb は、n 個の中から r 個を選ぶ組み合わせの番号 value を組み合わせ comb に変換します。実際の処理は関数 toComb で行います。
関数 toComb は組み合わせ comb の上位ビットから決定していきます。たとえば、n = 6, r = 3 の場合、ビットが 1 になるのは 5C2 = 10 通りあり、0 になるのは 5C3 = 10 通りあります。したがって、数値が 0 - 9 の場合はビットを 0 にし、10 - 19 の場合はビットを 1 にすればいいわけです。ビットを 0 にした場合、残りは 5C3 = 10 通りになるので、同様に次のビットを決定します。ビットを 1 にした場合、残りは 5C2 = 10 通りになります。数値から 5C3 = 10 を引いて次のビットを決定します。
プログラムでは、n-1Cr の値を関数 ncr で求めて変数 k にセットします。value が k 以上であれば comb の n - 1 番目のビットを 1 にセットし、value から k を引き算します。そして、次のビットを決めればいいわけです。r = 0 になったら comb を返します。また、r が n と等しくなったら、comb の残りのビットを全て 1 にセットした値を返します。
今回のプログラムは組み合わせの数を関数 ncr で求めています。もしも、実行速度が気になる場合は、あらかじめ組み合わせの数 nＣr を計算して配列に格納しておき、そこから値を求めるようにするといいでしょう。
最後に簡単なテストプログラムを作ります。
List : テストプログラム
fun test( n, r ) =
let
val m = ncr( n, r )
val i = ref 0
val c = ref 0w0
in
while !i < m do (
c := num_to_comb( n, r, !i );
print( Int.toString( !i ) ^ " -> " ^ Word.toString( !c ) );
print( " -> " ^ Int.toString( comb_to_num( n, r, !c ) ) ^ "\n" );
i := !i + 1
)
end
たとえば test( 6, 3 ) の場合、0 から 19 までの番号を関数 num_to_comb で組み合わせに変換し、その値を関数 comb_to_num で番号に戻します。実行結果は次のようになります。
- test( 6, 3 ); 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 10 -> 23 -> 10 11 -> 25 -> 11 12 -> 26 -> 12 13 -> 29 -> 13 14 -> 2a -> 14 15 -> 2c -> 15 16 -> 31 -> 16 17 -> 32 -> 17 18 -> 34 -> 18 19 -> 38 -> 19 val it = () : unit
正常に動作していますね。この方法を使うと、n 個ある組み合わせの中の i 番目 (0 <= i < n) の組み合わせを簡単に求めることができます。