読者です 読者をやめる 読者になる 読者になる

Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

perms

昨日に引き続き,「珠玉のリスト・プログラミング」に取り組みました。なんとか2問解けたので,3問目に挑戦です。

3問目はこんな問題です。

  • 与えられたリストの順列を生成する関数 perms

関数permsを実装する際,関数interleaveを使用するので,昨日,作成したinterleave.scmをモジュール化してみます。モジュール作成の練習です。こんな感じでしょうか?

interleave.scm

(define-module interleave
  (export interleave))
(select-module interleave)

(define interleave
  (lambda (x lst)
    (cond
     ((null? lst) (cons (cons x '()) '()))
     (else
      (cons
       (cons x lst)
       (helper-interleave (car lst) (interleave x (cdr lst))))))))

(define helper-interleave
  (lambda (x lst)
    (cond
     ((null? (cdr lst))
      (cons (cons x (car lst)) '()))
     (else
      (cons (cons x (car lst))
            (helper-interleave x (cdr lst)))))))

そして,いよいよ関数permsの実装です。

perms.scm

(use interleave)

(define perms
  (lambda (lst)
    (cond
     ((null? lst) '(()))
     (else
      (helper-perms (car lst) (perms (cdr lst)))))))

(define helper-perms
  (lambda (x lst)
    (cond
     ((null? lst) '())
     (else
      (append (interleave x (car lst))
              (helper-perms x (cdr lst)))))))

実行させてみます。

gosh> (write (perms '()))
(())#<undef>
gosh> (write (perms '(3)))
((3))#<undef>
gosh> (write (perms '(2 3)))
((2 3) (3 2))#<undef>
gosh> (write (perms '(1 2 3)))
((1 2 3) (2 1 3) (2 3 1) (1 3 2) (3 1 2) (3 2 1))#<undef>

どうやら,ちゃんと動いているようです(^^)。Schemeが楽しくなってきました。