Problem 24 - 順列(1)

Scheme

Vimごと落ちた。失敗。

Problem 24 - PukiWiki

(define (permutations s)
  (define (flatmap proc seq)
    (apply append (map proc seq)))
  (define (remove-1 item sequence)
    (cond ((null? sequence) '())
          ((equal? (car sequence) item) (cdr sequence))
          (else (cons (car sequence)
                      (remove-1 item (cdr sequence))))))
  (if (null? s)
      (list '())
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove-1 x s))))
               s)))

(list-ref (permutations (iota 3)) (- 6 1)) ; (2 1 0)
(list-ref (permutations (iota 10)) (- 1000000 1)) ; 落ちた

実行すると・・・一瞬でメモリ不足に。

GC Warning: Out of Memory!  Returning NIL!
Vim: Caught deadly signal SEGV
Vim: preserving files...
Vim: Finished.

リストの総数は、(10! * 10)個になるけど、耐えきれなかった様子。

練り直し。

追記

Gaucheでやってみたらメモリ不足にはならなかった。

gosh> (list-ref (permutations (iota 10)) (- 1000000 1))
(2 7 8 3 9 1 5 4 6 0)

おぉ。

単体のMzSchemeもなんとか大丈夫(2Gだとswapに手が出るか出ないかという感じ。ギリギリ)

メモリ消費量はGaucheに軍配。2割程少ない。


Vim組み込みのMzSchemeだと、swapが使えないっぽい。大量のメモリを使う場合、Vim組み込みは止めた方がいい。