順列生成ストリーム版

実は動いているのかも

昨日，ストリームを使ったアパート問題のプログラムがすんなり動かないと書いたが，実は遅いだけで，正しく動いているのかも…．

とりあえず，今日は順列生成のストリーム版について書いてみる．いや，本当は順列というより，置換と言うべきなのかな．n個の異なる数からn個を選ぶのだから．

リスト版のpermutations

リスト版のpermutationsは，昨日のプログラムにもあるように，Gaucheの場合util.combinationsに含まれているけど，ストリーム版のpermutationsを作る準備として，まずはリスト版のpermutationsを作ってみる．

SICPにあるのは覚えていたが，ちゃんと書けるかどうか，力試しのつもりで見ずに書いたら，結構な時間がかかってしまった…．というか，関数名のヒントなしには一週間後にパッと読む自信がないが，Schemerなら普通スラスラ読めるのだろうか？

(use srfi-1)
(define (permutations l)
  (if (null? l)
      (list '())
      (append-map (lambda (x)
                    (map (lambda (y) (cons x y))
                         (permutations (remove (lambda (z) (= z x)) l))))
                  l)))

ストリーム版のpermutations

stream-apppend-mapより，stream-foldの方が書きやすかったので，それを使う以外は，上記プログラムをほぼ機械的に変換したのが下記のストリーム版．

(use util.stream)

(define (stream-fold f seed l)
  (stream-delay
   (if (stream-null? l)
       seed
       (stream-fold f (f seed (stream-car l)) (stream-cdr l)))))

(define (stream-remove x l)
  (stream-delay (stream-filter (lambda (i) (not (= i x))) l)))

(define (stream-permutations l)
  (stream-delay
   (if (stream-null? l)
       (stream-cons stream-null stream-null)
       (stream-fold
        stream-append stream-null
        (stream-map (lambda (x)
                      (stream-map (lambda (y) (stream-cons x y))
                                  (stream-permutations (stream-remove x l))))
                    l)))))

下記のテストであまり待たされないところを見ると，どうやらうまく動いているらしい．

(define (main args)
  (let ((p (stream-permutations (stream-iota 20 1))))
    (print (stream->list (stream-ref p 50)))))

後は，stream-permutationsを決定性計算版のアパート問題プログラムに組み込めばいいはず．

ストリーム版のpermutations，本当はもとの意図と違っている

本当は，stream->listを使わなくても，(stream-ref p 50)などとすれば，順列がひとつリストとして取り出せるようなストリームが書きたかったのだが，どうやっていいのかわからない．うまい方法はあるのだろうか…．それとも，こういう場合はストリームの各要素もストリームになるように作るのが定石なのだろうか…．