2009/01/28

[scheme][Gauche][DrScheme]組み合わせ(combination)

 

この記事を見て、組み合わせを書いてみたくなり、書いてみました。
[アルゴリズム][C#2.0][C#3.0]C#で順列(Permutation)と組み合わせ(Combination)をすべて列挙してみよう
http://d.hatena.ne.jp/zecl/20090127/p1

 

 

結局この辺をカンニングしまくりorz

 

[scheme]組合せのアルゴリズム
http://d.hatena.ne.jp/ibaza/20080303/1204476552

 

ArcでL-99 (P26 リストから指定した個数を抜き出す組み合わせ)
http://cadr.g.hatena.ne.jp/g000001/20080302/1204443536

 

組合せ
http://katamayu.net/archives/2006/05/11/012239

 

 

最初に書いてみたcombination手続き。

参考にしたのは[scheme]組合せのアルゴリズムのこのアルゴリズム。

nCr(n個からr個取り出す組合せ)は、


1. リストの先頭要素を除いた残りのリストからr-1個を選ぶ組合せのそれぞれに先頭要素を加えたものと、


2. リストの先頭要素を除いたリストからr個を選ぶ組合せ
の合計となる(1および2はそれぞれ再帰処理となる)。


3. n = r のときは選び方は一つなのでリストをそのままリストにして返す。例:(a b c) なら ((a b c)) にして返す


4. r = 1 のときは選び方はn通りあるのでリストの要素をそれぞれリストにして返す。例:(a b c) なら ((a) (b) (c)) にして返す


5. r = 0 または r がリストの要素数より大きいときは空リストを返す。

 

で、上記のアルゴリズムをそのまま写経したつもりなのがこれ。

;; combination
(define (combination ls r)
  (cond
   ((or (null? ls)(null? ls)) '())
   ((or (zero? r)(> r (length ls))) '())
   ((= r 1)(map list ls))
   ((= r (length ls))(list ls))
   (else
    (cons (map (lambda (n)(cons (car ls) n))(combination (cdr ls)(- r 1)))
        (combination (cdr ls) r)))))

 

 

出力結果。
出力結果のリストがネストしてる・・・。

(combination '() 1) ;; => ()
(combination '(1 2 3) 4) ;; => ()
(combination '(1 2 3) 1) ;; => ((1) (2) (3))
(combination '(1 2 3) 3) ;; => ((1 2 3))
(combination '(1 2 3 4 5) 2)
;; => (((1 2) (1 3) (1 4) (1 5)) ((2 3) (2 4) (2 5)) ((3 4) (3 5)) (4 5))
(combination '(1 2 3 4 5) 3)
;; => (((1 (2 3) (2 4) (2 5)) (1 (3 4) (3 5)) (1 . #0=(4 5))) ((2 (3 4) (3 5)) (2 . #0#)) (3 . #0#))
(combination '(1 2 3 4 5) 4)
;; => (((1 (2 (3 4) (3 5)) (2 . #0=(4 5))) (1 . #1=(3 . #0#))) (2 . #1#))

 

 

cond ~ elseのelseのとこのconsがまずいことに気づく。
組合せをみてappend手続きがあることを知る。修正版combination。

;; combination
(define (combination ls r)
  (cond
   ((or (null? ls)(null? ls)) '())
   ((or (zero? r)(> r (length ls))) '())
   ((= r 1)(map list ls))
   ((= r (length ls))(list ls))
   (else
    (append (map (lambda (n)(cons (car ls) n))
         (combination (cdr ls)(- r 1)))
        (combination (cdr ls) r)))))

 

 

出力結果。
今度はうまくいったはず!と、思いきや「#0=」「#1=」「#0#」「#1#」ってのが混ざってる・・・。これなに?なんか変な対ができてる・・・orz

(combination '() 1) ;; => ()
(combination '(1 2 3) 4) ;; => ()
(combination '(1 2 3) 1) ;; => ((1) (2) (3))
(combination '(1 2 3) 3) ;; => ((1 2 3))
(combination '(1 2 3 4 5) 2)
;; => ((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))
(combination '(1 2 3 4 5) 3)
;; => ((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 . #0=(4 5)) (2 3 4) (2 3 5) (2 . #0#) (3 . #0#))
(combination '(1 2 3 4 5) 4)
;; => ((1 2 3 4) (1 2 3 5) (1 2 . #0=(4 5)) (1 . #1=(3 . #0#)) (2 . #1#))

 

 

試しに同じcombination手続きをDrSchemeで実行してみたら、意図した通りに出力されてるっぽいのに・・・。

;; combination
(define (combination ls r)
  (cond
   ((or (null? ls)(null? ls)) '())
   ((or (zero? r)(> r (length ls))) '())
   ((= r 1)(map list ls))
   ((= r (length ls))(list ls))
   (else
    (append (map (lambda (n)(cons (car ls) n))
         (combination (cdr ls)(- r 1)))
        (combination (cdr ls) r)))))

(combination '() 1)
(combination '(1 2 3) 4)
(combination '(1 2 3) 1)
(combination '(1 2 3) 3)
(combination '(1 2 3 4 5) 2)
(combination '(1 2 3 4 5) 3)
(combination '(1 2 3 4 5) 4)

 

 

DrSchemeでの実行結果。うまくいってるっぽい・・・。

()
()
((1) (2) (3))
((1 2 3))
((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (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))
((1 2 3 4) (1 2 3 5) (1 2 4 5) (1 3 4 5) (2 3 4 5))

 

 

 

Gauche(gosh)でのこの結果はどういうこと?

;; => ((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))
(combination '(1 2 3 4 5) 3)
;; => ((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 . #0=(4 5)) (2 3 4) (2 3 5) (2 . #0#) (3 . #0#))
(combination '(1 2 3 4 5) 4)
;; => ((1 2 3 4) (1 2 3 5) (1 2 . #0=(4 5)) (1 . #1=(3 . #0#)) (2 . #1#))

 

 

追記:

Twitterにて

valvallow Gauche  で #0# とか #0=  とか #1= とか出力されちゃってる状態なんだけど、これなに?
valvallow (((1 (2 (3 4) (3 5)) (2 . #0=(4 5))) (1 . #1=(3 . #0#))) (2 . #1#))
valvallow みたいな
valvallow gosh> ((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 . #0=(4 5)) (2 3 4) (2 3 5) (2 . #0#) (3 . #0#))
valvallow DrScheme で同じコード実行してもでてこねー。
kosugi @valvallow 同じオブジェクト参照の意じゃないかな
valvallow @kosugi  なるほど!ぽいですね!ありがとうございます><

0 件のコメント:

コメントを投稿