組合せの生成

;;; combination.scm
(define (getbits n int)
  (let loop((index 0) (bits '()))
    (if (= index n)
	(map (lambda (b) (if b 1 0)) bits)
	(loop (+ index 1) (cons (logbit? index int) bits)))))

(define (next-combination current)
  (let ((sb (lambda (x) (logand x (- x)))))
    (let* ((s (sb current))
	   (r (+ current s)))
      (logior r (- (ash (/ (sb r) s) -1) 1)))))

(define (first-combination k)
  (- (ash 1 k) 1))

(define (generate-combination n k)
  (letrec ((max (first-combination n))
	   (iter (lambda (c lis)
		   (if (<= c max)
		       (iter (next-combination c) (cons c lis))
		       lis))))
    (iter (first-combination k) '())))

(define (make-combination n k)
  (map (lambda (x) (getbits n x)) (generate-combination n k)))

実行例

gosh> (load "./combination.scm")
#t
gosh> (for-each print (make-conbination 5 2))
(1 1 0 0 0)
(1 0 1 0 0)
(1 0 0 1 0)
(1 0 0 0 1)
(0 1 1 0 0)
(0 1 0 1 0)
(0 1 0 0 1)
(0 0 1 1 0)
(0 0 1 0 1)
(0 0 0 1 1)
#<undef>

組み合わせの表現

「n個の異なるものからk個選ぶ選び方」をn bitの数のうちk個のbitが1、他が0というふうに表す。例えばn=8, k=4なら10011100とか11000110とか。

このようにすると組合せがnビットの整数に対応するので、各組合せの間で大小比較ができる。n=8,k=4のもとで「最小」の組合せは00001111で、その次が00010111で、という具合に最小のものから始めて次々に組合せをみつけていくことができる。

「次」の組合せの生成

10011100の次は10100011になる。これを以下のように生成する。

1. 元の組合せ10011100において、1になっている中で最下位のビットを見つけて、そのビットが1でそれより右が0の数s:=100を生成して元の数に加える。→10100000を得る。
2. 得た10100000でも同様に1になっている中で最下位のビットが1、それより右が0の数ns:=100000を得る。
3. ここで比 ns/s = 1000 は1番目の操作で繰り上がって「0に変化した1の多さ」の情報を有している。ns/s を右に1つビットシフトして1引くことで失われた分だけの1が出現する。これを2で得た10100000に足すと「次」の組合せである10100011を得る。

わかったようなわかってないような説明ですみません。この方法の「心」はまだつかめてない感じだなぁ〜。

参考文献

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

ほとんどこの本の60ページの通りです。

計算量

組合せの数と同じオーダーというのがすごい。それでもnを大きくしたりするとnCk = n!/k!(n-k)!なので時間かかりますが…。