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が楽しくなってきました。