この記事を見て、組み合わせを書いてみたくなり、書いてみました。
[アルゴリズム][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 件のコメント:
コメントを投稿