前回はクロージャについて説明しました。初心者の方にとって、クロージャはちょっと難しい話だったかもしれません。今回は一息入れて「順列 (permutation) 」と「組み合わせ (combination) 」を取り上げます。なお、Gauche には順列と組み合わせを求めるライブラリ (util.combinations) が用意されていますが、Scheme のお勉強ということで実際にプログラムを作ってみましょう。
たとえば 4 つの整数 1, 2, 3, 4 の順列は次に示すように 24 通りあります。
1 2 3 4, 1 2 4 3, 1 3 2 4, 1 3 4 2, 1 4 2 3, 1 4 3 2 2 1 3 4, 2 1 4 3, 2 3 1 4, 2 3 4 1, 2 4 1 3, 2 4 3 1 3 1 2 4, 3 1 4 2, 3 2 1 4, 3 2 4 1, 3 4 1 2, 3 4 2 1 4 1 2 3, 4 1 3 2, 4 2 1 3, 4 2 3 1, 4 3 1 2, 4 3 2 1
一般に、異なる n 個の順列の総数は、n の階乗 (n!) 通りだけあります。この順列をすべて求めるプログラムを考えてみましょう。このときよく使われる方法に「バックトラック法 (backtracking) 」があります。
たとえば、簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけませんね。つまり、失敗したら後戻りして別の道を選ぶ、という試行錯誤をゴールに行き着くまで繰り返すわけです。これがバックトラック法の基本的な考え方です。
バックトラック法は迷路を解くだけではなく、いろいろな問題に応用できる方法です。とくに、すべての解を求める場合、バックトラック法が適しています。すべての解をもれなく見つけることができます。
順列は次のような図を書くと簡単に求めることができます。
START ──１─┬─２─┬─３──４ ──→ 1 2 3 4
│ │
│ └─４──３ ──→ 1 2 4 3
│
├─３─┬─２──４ ──→ 1 3 2 4
│ │
│ └─４──２ ──→ 1 3 4 2
│
└─４─┬─２──３ ──→ 1 4 2 3
│
└─３──２ ──→ 1 4 3 2
図 : 順列の生成
上図は 1 から始まる場合です。同様に 2, 3, 4 から始まる図があります。最初が 1 であれば、次の数は 2, 3, 4 の中から選ばれますね。したがって、1 から 2, 3, 4 へと枝分かれします。1-2 と選んだ場合、次は 3, 4 の中から数を選びます。今度は 2 から 3, 4 へと枝分かれします。1-2-3 と選んだ場合は、残った数は 1 つしかありませんね。その数 4 を選んで 1-2-3-4 という並べ方が完成します。
ほかの並べ方を求めるには、今まで通った道を戻って別の道を探します。まず、1-2-3-4 から 1-2-3 まで後戻りします。この地点では 4 以外の道はないので、もうひとつ戻らなくてはいけません。1-2 まで戻ると、道は 2 つに枝分かれしています。3 はすでに通った道ですから、今度は 4 を選ぶことになります。この道を進んでいくと、1-2-4-3 という並べ方を求めることができます。
再度 1-2 まで後戻りします。2 つの道ともすでに通ったことがあるので、1 の位置まで後戻りします。この地点は 3 つに枝分かれしていますが、2 の道は通ったので今度は 3 を選んで 1-3 へ進みます。このように、通ったことがない道を選んでいき、1 から枝分かれする道をすべて通ったならば、START まで戻って 1 以外の道を選ぶことになります。あとは同様に道をたどっていけば、すべての並べ方を求めることができます。
それでは、プログラムを作ってみます。ここまでの説明で、バックトラック法の実現は難しいのではないか、と思った方はいませんか。「進む」ことと「戻る」ことをどのようにプログラムしたらよいのか、見当もつかないという人もいるかもしれません。ところがバックトラック法は、今までに何回も使ってきた「再帰呼び出し」を利用すると、とても簡単に実現できるのです。
まず、「進む」場合を再帰呼び出しに対応させます。そうすると、ひとつ手前の位置に戻ることは、呼び出し元の関数に戻ることに対応させることができるのです。つまり、関数の評価を終了すれば、元の位置に「バックトラック」できるわけです。
具体的に説明しましょう。まず、順列を生成する関数を perm と定義します。perm の第 1 引数には選択していない数を格納したリストを渡し、第 2 引数には選んだ数を格納するリストを渡します。最初に呼び出すときは、次のようになります。
(perm '(1 2 3 4) '())
まだ数を選択していないので、第 1 引数は (1 2 3 4) となり、第 2 引数は () となります。数は第 1 引数のリストの中から選びます。再帰呼び出しする場合、選んだ数をリストから削除するとともに、第 2 引数のリストへ追加します。次の図を見てください。
perm 第 1 引数 第 2 引数
----------------------------------
│ (1 2 3 4) ()
│ ^
再 ↓
帰 │ (2 3 4) (1)
呼 │ ^
び ↓
出 │ (3 4) (2 1)
し │ ^
↓
│ (4) (3 2 1)
│ ^
↓
() (4 3 2 1) 並べ方完成
図 : 関数 perm の動作（その１）
最初は (1 2 3 4) の中から数を選びます。このとき、リストの先頭から順番に数を選んでいきます。最初は 1 を選びますが、バックトラックしたときは、次の 2 を選ぶようにします。再帰呼び出しするときは、第 1 引数のリストから 1 を削除し、それを第 2 引数のリストに追加します。数はリストの先頭へ追加していくので、並べ方が逆になることに注意してください。
このように、再帰呼び出しを続けていくと、第 1 引数は空リストになります。ここが、再帰呼び出しの停止条件となり、第 2 引数には数の並びが逆順にセットされています。これを出力すればいいわけです。
次に、新しい組み合わせを探すため、バックトラックを行います。次の図を見てください。
perm 第 1 引数 第 2 引数
-----------------------------------
│ nil (4 3 2 1)
バック │
トラック↓
│ (4) (3 2 1)
バック │ X
トラック↓
│ (3 4) (2 1)
再帰 │ X ^
↓
│ (3) (4 2 1)
再帰 │ ^
↓
() (3 4 2 1) 組み合わせ完成
図 : 関数 perm の動作（その２）
バックトラックすると、第 1 引数が (4) で第 2 引数が (3 2 1) の状態に戻ります。ここで、次の数を選ぶのですが、もうリストには数がありません。そこで、再度バックトラックします。すると、第 1 引数が (3 4) で第 2 引数が (2 1) の状態に戻ります。このときは、3 の次である 4 を選びます。第 1 引数 (3 4) から 4 を取り除いた (3) と、第 2 引数 (2 1) に 4 を追加した (4 2 1) を与えて再帰呼び出しします。あとは、同じことを繰り返すことで、順列をすべて求めることができるわけです。
それでは、プログラムを示します。
リスト ; 順列の生成
(use srfi-1)
; 引数 x と等しい要素を削除
(define (remove-item x ls)
(remove (lambda (a) (equal? a x)) ls))
; 順列の生成
(define (perm ls a)
(if (null? ls)
(format #t "~A~%" (reverse a))
(for-each
(lambda (n)
(perm (remove-item n ls) (cons n a)))
ls)))
最初に、(use srfi-1) でリスト操作ライブラリ srfi-1 をロードします。Gauche の場合、これで srfi-1 に定義されている関数を使うことができます。次に、リストの中から要素を削除する関数 remove-item を定義します。この処理は srfi-1 の関数 remove を使うと簡単です。等値関係は equal? でテストします。これで数値だけではなく、シンボルや文字列
にも対応することができます。最後に関数 perm を作ります。引数 ls が数字を格納するリストで、引数 a に選んだ数字が格納されます。ls が空リストの場合、順列がひとつ完成したので、format で画面へ出力します。reverse でリストを反転していることに注意してください。
そうでなければ、第 1 引数のリストから数を順番に選んでいきます。この処理は for-each という高階関数を使うと簡単です。
for-each は R5RS に定義されている関数で、引数のリストから順番に要素を取り出して、それを引数 func に渡して評価します。map と違って for-each は func を呼び出すだけであり、func の返り値は捨てられます。for-each は副作用を目的とした関数を呼び出すときに使います。Gauche の場合、for-each の返り値は #<undef> です。
簡単な例を示しましょう。
gosh> (define (foo x) (display x) (newline)) foo gosh> (for-each foo '(1 2 3 4 5)) 1 2 3 4 5 #<undef>
perm の説明に戻ります。for-each の繰り返しが終了すれば perm の評価も終了するので、選ぶ数がなくなったらバックトラックするという処理を実現することができます。
それでは実行してみましょう。
gosh> (perm '(1 2 3 4) '()) (1 2 3 4) ・・省略・・ (4 3 2 1) gosh> (perm '(1 2 3) '()) (1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)
正常に動作していますね。
ところで、関数 perm は順列を画面へ出力しましたが、高階関数にしたほうが便利でしょう。プログラムは次のようになります。
リスト : 順列の生成 (高階関数版)
(define (permutations func ls)
(define (perm ls a)
(if (null? ls)
(func (reverse a))
(for-each
(lambda (n)
(perm (remove-item n ls) (cons n a)))
ls)))
(perm ls '()))
関数 permutations の引数 func が関数で、ls がリストです。内部関数 perm は、順列を表示する処理を関数 func の呼び出しに変えただけです。あとは、内部関数 perm を呼び出すだけです。とても簡単ですね。たとえば、(lambda (x) (format #t "~A~%" x)) を渡せば、順列をすべて表示することができます。
生成した順列をリストに格納して返す場合は、畳み込み関数 fold-right を使うと簡単です。プログラムは次のようになります。
リスト : 順列の生成 (2)
(define (permutations-list ls)
(define (perm ls a b)
(if (null? ls)
(cons (reverse a) b)
(fold-right
(lambda (x y)
(perm (remove-item x ls) (cons x a) y))
b
ls)))
(perm ls '() '()))
内部関数 perm は生成した順列を引数 b のリストに格納して、それをそのまま返します。perm を呼び出す場合、この返り値を引数 b に渡すことで、生成した順列を格納していくことができます。ここで fold-right が役に立ちます。
fold-right の初期値を perm の引数 b にすることで、ラムダ式 (lambda (x y) ...) の引数 y に順列を格納するリストを渡します。あとは perm を再帰呼び出しすると、その返り値は次にラムダ式 (lambda (x y) ...) を呼び出すときの引数 y に渡されるので、順列を格納したリストを perm に渡していくことができます。
それでは実行結果を示します。
gosh> (permutations-list '(1 2 3)) ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
正常に動作していますね。
次は組み合わせの数を求めるプログラムを作ってみましょう。組み合わせの数 nＣr を求めるには、次の公式を使えば簡単です。
nＣr = n * (n - 1) * (n - 2) * ... * (n - r + 1) / (1 * 2 * 3 * ... * r)
皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。Scheme は多倍長演算をサポートしているので、桁あふれを心配する必要はありません。
この公式をそのままプログラムすることもできますが、次の式を使うともっと簡単にプログラムできます。
nＣr = nＣr-1 * (n - r + 1) / r nＣ0 = nＣn = 1
この式は nＣr と nＣr-1 の関係を表しています。あとは階乗と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。
リスト : 組み合わせの数を求める
(define (num-comb n r)
(if (or (zero? n) (zero? r))
1
(/ (* (num-comb n (- r 1)) (+ (- n r) 1)) r)))
Scheme (Lisp) では、複数の述語を組み合わせた複雑なテストを行う場合、and と or を使って実現することができます。
関数 and はシンタックス形式で、複数の述語を「～かつ～」で結ぶ働きをします。and は与えられた述語を左から順番に評価します。そして、述語の評価結果が #f であれば、残りの述語を評価せずに #f を返します。ただし、最後まで述語が #f に評価されなかった場合は、いちばん最後の評価結果を返します。ひらたくいえば、すべての述語が条件を満たさない限り and は真に評価されません。
関数 or もシンタックス形式で、複数の述語を「～または～」で結ぶ働きをします。or は and と違い、述語の評価結果が #f 以外の場合に、残りの述語を評価せずにその評価結果を返します。すべての述語が #f に評価された場合は #f を返します。つまり、どれかひとつの述語が条件を満たせば or は真に評価されます。
プログラムはとても簡単ですね。ところで、整数値の範囲が限られているプログラミング言語では、この方法でも桁あふれする場合があるので注意してください。
それでは、関数 num-comb を使って「パスカルの三角形」を作ってみましょう。次の図を見てください。
１ 0Ｃ0
／ ＼ ／ ＼
１ １ 1Ｃ0 1Ｃ1
／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ２ １ 2Ｃ0 2Ｃ1 2Ｃ2
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ３ ３ １ 3Ｃ0 3Ｃ1 3Ｃ2 3Ｃ3
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
１ ４ ６ ４ １ 4Ｃ0 4Ｃ1 4Ｃ2 4Ｃ3 4Ｃ4
図 : パスカルの三角形
パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは式 (a + b)n を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 nＣr に対応しています。
きれいな三角形にはなりませんが、簡単なプログラムを示します。
リスト : パスカルの三角形
(define (pascal x)
(let loop1 ((n 0))
(cond ((<= n x)
(let loop2 ((r 0))
(cond ((<= r n)
(format #t "~6D" (num-comb n r))
(loop2 (+ r 1)))))
(newline)
(loop1 (+ n 1))))))
名前付き let で二重ループを構成しています。loop1 の繰り返しの中に loop2 の繰り返しがあり、loop1 で変数 n の値を 0 から x まで +1 ずつ増やし、loop2 で変数 r の値を 0 から n まで +1 ずつ増やします。あとは num-comb で nＣr の値を計算するだけです。
実行結果は次のようになります。
gosh> (pascal 10)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
上図のように、きれいな三角形を出力するプログラムは、皆さんにお任せいたします。また、関数 num-comb を使わないでパスカルの三角形を出力するプログラムを作ってみるのもよいでしょう。
今度は nCr 個の組み合わせを全て生成するプログラムを作ってみましょう。たとえば、1 から 5 までの数字の中から 3 個を選ぶ組み合わせは次のようになります。
(1 2 3), (1 2 4), (1 2 5), (1 3 4), (1 3 5), (1 4 5), (2 3 4), (2 3 5), (2 4 5), (3 4 5)
最初に 1 を選択した場合、次は (2 3 4 5) の中から 2 個を選べばいいですね。2 番目に 2 を選択したら、次は (3 4 5) の中から 1 個を選べばいいわけです。これで、(1 2 3), (1 2 4), (1 2 5) が生成されます。(2 3 4 5) の中から 2 個選ぶとき、2 を選ばない場合があります。この場合は (3 4 5) の中から 2 個を選べばいいわけです。ここで 3 を選ぶと (1 3 4), (1 3 5) が生成できます。同様に、3 を除いた (4 5) の中から 2 個を選ぶと (1 4 5) を生成することができます。
これで 1 を含む組み合わせを生成したので、次は 1 を含まない組み合わせ、つまり (2 3 4 5) から 3 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は次に示す組み合わせの公式と同じです。
nＣ0 = nＣn = 1 nＣr = n-1Ｃr-1 + n-1Ｃr
Scheme でプログラムを作ると次のようになります。
リスト : 組み合わせの生成
(define (combinations func n ls)
(define (comb n ls a)
(cond ((zero? n)
(func (reverse a)))
((= (length ls) n)
(func (append (reverse a) ls)))
(else
(comb (- n 1) (cdr ls) (cons (car ls) a))
(comb n (cdr ls) a))))
(if (> n (length ls))
#f
(comb n ls '())))
関数 combinations は引数 ls のリストから n 個を選ぶ組み合わせを生成して関数 func を適用します。実際の処理は内部関数 comb で行います。選んだ数字は第 3 引数 a のリストに格納します。n が 0 になったら組み合わせを一つ生成できたので、a を reverse で逆順にして func を呼び出します。
次の節で、リスト ls の長さが n と等しくなったならば、リストの要素を全て選択します。reverse で a を逆順にして append でリスト ls と結合してから func を呼び出します。この 2 つの条件が再帰呼び出しの停止条件になります。
あとは関数 comb を再帰呼び出しするだけです。最初の呼び出しは先頭の要素を選択する場合です。先頭要素を a に追加して、リスト (cdr ls) の中から n - 1 個を選びます。最後の呼び出しが先頭の要素を選ばない場合です。リスト (cdr ls) の中から n 個を選びます。
プログラムはこれで完成です。簡単な実行例を示しましょう。
gosh> (combinations (lambda (x) (display x) (newline)) 3 '(1 2 3 4 5)) (1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5)
正常に動作していますね。
生成した組み合わせをリストに格納して返す場合も簡単です。プログラムは次のようになります。
リスト : 組み合わせの生成 (リストに格納)
(define (combinations-list n ls)
(define (comb n ls a b)
(cond ((zero? n)
(cons (reverse a) b))
((= (length ls) n)
(cons (append (reverse a) ls) b))
(else
(comb (- n 1)
(cdr ls)
(cons (car ls) a)
(comb n (cdr ls) a b)))))
(if (> n (length ls))
#f
(comb n ls '() '())))
内部関数 comb は、生成した組み合わせを引数 b のリストに格納し、それをそのまま返します。comb を呼び出す場合、この返り値を引数 b に渡すことで、生成した組み合わせを格納していくことができます。具体的には、comb を再帰呼び出しするところで、1 回目の呼び出しの返り値を 2 回目の呼び出しの第 4 引数に渡します。これで生成した組み合わせをリストに格納することができます。
それでは実行結果を示します。
gosh> (combinations-list 3 '(1 2 3 4 5)) ((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5))
正常に動作していますね。
次は n 個の中から r 個を選ぶ組み合わせをビットのオンオフで表してみましょう。たとえば、5 個の数字 (0 - 4) から 3 個を選ぶ場合、数字を 0 bit から 4 bit に対応させます。すると、1, 3, 4 という組み合わせは 11010 と表すことができます。これを Scheme でプログラムすると次のようになります。
リスト : 組み合わせの生成 (2)
(define (combinations1 func n r)
(define (comb n r a)
(cond ((zero? r) (func a))
((= n r)
(func (+ (expt 2 r) -1 a)))
(else
(comb (- n 1) r a)
(comb (- n 1) (- r 1) (+ (expt 2 (- n 1)) a)))))
(if (< n r)
#f
(comb n r 0)))
関数 combinations1 は n 個の中から r 個を選ぶ組み合わせを生成して出力します。実際の処理は内部関数 comb で行います。組み合わせは引数 a にセットします。r が 0 になったら、組み合わせがひとつできたので関数 func を呼び出します。
n が r と等しくなったならば、残り r 個をすべて選びます。0 から r - 1 番目のビットを全部オンにするため 2r - 1 を計算し、それを引数 a に加算します。これで r 個のビットをオンにすることができます。
あとは comb を再帰呼び出しします。最初の呼び出しは n 番目の要素を選ばない場合です。n - 1 個の中から r 個を選びます。次の呼び出しが n 番目の要素を選ぶ場合です。2n-1 を計算して、それを a に加算します。これで、n - 1 番目のビットをオンにすることができます。そして、n - 1 個の中から r - 1 個を選びます。
それでは 5 個の中から 3 個を選ぶ combinations1 の実行例を示します。
gosh> (combinations1 (lambda (x) (format #t "~5,'0B~%" x)) 5 3) 00111 01011 01101 01110 10011 10101 10110 11001 11010 11100
この場合、最小値は 00111 (7) で最大値は 11100 (#x1c) になります。このように、combinations1 は組み合わせを表す数を昇順で出力します。ところで、参考文献 1 の「組み合わせの生成」には、再帰呼び出しを使わずに同じ結果を得る方法が解説されてます。とても巧妙な方法なので、興味のある方は読んでみてください。
次は、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Ｃ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 番目となります。
このように、数字を選ぶときに、数字を選ばない場合の組み合わせの数を足し算していけば、その組み合わせの番号を求めることができるのです。プログラムは次のようになります。
リスト : 組み合わせに番号を付ける
(define (comb-to-num n r c)
(define (to-num n r value)
(cond ((or (zero? r) (= n r)) value)
((logbit? (- n 1) c)
(to-num (- n 1) (- r 1) (+ (num-comb (- n 1) r) value)))
(else
(to-num (- n 1) r value))))
(to-num n r 0))
関数 comb-to-num は n 個の中から r 個を選ぶ組み合わせ c を番号に変換します。実際の処理は内部関数 to-num で行います。to-num は c の上位ビットから順番にチェックしていきます。ビットのチェックは述語 logbit? を使います。Gauche にはビット演算を行う関数が用意されています。ここで簡単に説明しましょう。
logbit? は添字 index の位置にある整数値 n のビットが 1 ならば真 (#t) を返します。逆に 0 ならば偽 (#f) を返します。
引数に対するビットごとの論理積、論理和、排他的論理和を返します。
lognot は整数 n のビットごとの否定を返します。logcount は整数 n が正の値であれば 1 のビットを数えて返します。負の値であれば、0 のビットを数えて返します。
n 個の中から r 個を選ぶ場合、n - 1 番目のビットが 1 であれば n-1Ｃr の値を value に加算して to-num を再帰呼び出しします。このとき、n 個の中から一つ選んだので、r の値を -1 することをお忘れなく。ビットが 0 であれば、value の値はそのままで to-num を再帰呼び出しします。n = r または r = 0 になったら value を返します。これが再帰呼び出しの停止条件になります。
次は、番号から組み合わせを求める関数 num-to-comb を作ります。次のリストを見てください。
リスト : 番号から組み合わせを求める
(define (num-to-comb n r value)
(define (to-comb n r value c)
(if (= n r)
(+ (expt 2 n) -1 c)
(let ((k (num-comb (- n 1) r)))
(if (>= value k)
(to-comb (- n 1) (- r 1) (- value k) (+ (expt 2 (- n 1)) c))
(to-comb (- n 1) r value c)))))
(if (<= (num-comb n r) value)
#f
(to-comb n r value 0)))
関数 num-to-comb は、組み合わせ nＣr の番号 value を組み合わせ c に変換します。実際の処理は内部関数 to-comb で行います。関数 to-comb は組み合わせ c の上位ビットから決定していきます。
たとえば、n = 6, r = 3 の場合、ビットが 1 になるのは 5Ｃ2 = 10 通りあり、0 になるのは 5Ｃ3 = 10 通りあります。したがって、数値が 0 - 9 の場合はビットを 0 にし、10 - 19 の場合はビットを 1 にすればいいわけです。ビットを 0 にした場合、残りは 5Ｃ3 = 10 通りになるので、同様に次のビットを決定します。ビットを 1 にした場合、残りは 5Ｃ2 = 10 通りになります。数値から 5Ｃ3 = 10 を引いて次のビットを決定します。
プログラムでは、n-1Ｃr の値を関数 num-comb で求めて変数 k にセットします。value が k 以上であれば c の n - 1 番目のビットを 1 にセットし、value から k を引き算します。そして、次のビットを決めればいいわけです。r = 0 になったら c を返します。また、r が n と等しくなったら、c の残りのビットを全て 1 にセットした値を返します。
最後に簡単なテストプログラムを作ります。
リスト : テストプログラム
(define (test n r)
(let ((m (num-comb n r)))
(let loop ((i 0))
(if (< i m)
(let ((c (num-to-comb n r i)))
(format #t "~D -> ~B -> ~D~%" i c (comb-to-num n r c))
(loop (+ i 1)))))))
たとえば (test 6 3) の場合、0 から 19 までの番号を関数 num-to-comb で組み合わせに変換し、その値を関数 comb-to-num で番号に戻します。実行結果は次のようになります。
gosh> (test 6 3) 0 -> 111 -> 0 1 -> 1011 -> 1 2 -> 1101 -> 2 3 -> 1110 -> 3 4 -> 10011 -> 4 5 -> 10101 -> 5 6 -> 10110 -> 6 7 -> 11001 -> 7 8 -> 11010 -> 8 9 -> 11100 -> 9 10 -> 100011 -> 10 11 -> 100101 -> 11 12 -> 100110 -> 12 13 -> 101001 -> 13 14 -> 101010 -> 14 15 -> 101100 -> 15 16 -> 110001 -> 16 17 -> 110010 -> 17 18 -> 110100 -> 18 19 -> 111000 -> 19
正常に動作していますね。この方法を使うと、n 個ある組み合わせの中の i 番目 (0 <= i < n) の組み合わせを簡単に求めることができます。
今回はここまでです。簡単に復習しておきましょう。
次回はバックトラック法を使って簡単なパズルを解いてみましょう。お楽しみに。