暇なので解いてみた。
(define nil '()) (define (enumerate-interval low high) (if (> low high) nil (cons low (enumerate-interval (+ low 1) high)))) (define (accumulate op initial seq) (if (null? seq) initial (op (car seq) (accumulate op initial (cdr seq))))) (define (flatmap proc seq) (accumulate append nil (map proc seq))) (define (remove item seq) (filter (lambda (x) (not (eq? x item))) seq)) ;; (define (tonari n d) (define numbers (enumerate-interval 1 n)) (define (check ans) (define (iter-2 nums dd) (if (= (length nums) dd) #t (let ((a (car nums)) (b (list-ref nums dd))) (if (< (abs (- a b)) d) #f (iter-2 (cdr nums) dd))))) (define (iter-1 ans dd) (if (= dd d) #t (and (iter-2 ans dd) (iter-1 ans (+ dd 1))))) (if (>= (length ans) d) (iter-1 ans 1) #t)) (define (iter-2 ans num rests) (if (null? rests) (if (check ans) `(,ans) nil) (if (not (check ans)) nil (flatmap (lambda (x) (iter-2 (append ans `(,x)) x (remove x rests))) rests)))) (define (iter num ans) (if (> num n) ans (iter (+ num 1) (append ans (iter-2 (cons num nil) num (remove num numbers)))))) (if (>= d n) nil (iter 1 nil)))
ポイントは条件に合わない順列はなるべく早いうちに切り捨てて、すべての順列の組み合わせを作らないようにする事です。
順列の組み合わせをすべて作っていては、n = 9 でさえきついです。
結果
gosh> (tonari 9 3) ((3 6 9 2 5 8 1 4 7) (7 4 1 8 5 2 9 6 3))
順列の個数
gosh> (length (tonari 9 3)) 2 gosh> (length (tonari 10 3)) 40 gosh> (length (tonari 11 3)) 792 gosh> (length (tonari 12 3)) 15374 gosh> (length (tonari 13 3)) 281434
合ってそう。
処理時間
gosh> (time (length (tonari 9 3))) ;(time (length (tonari 9 3))) ; real 0.003 ; user 0.000 ; sys 0.000 2 gosh> (time (length (tonari 10 3))) ;(time (length (tonari 10 3))) ; real 0.015 ; user 0.016 ; sys 0.000 40 gosh> (time (length (tonari 11 3))) ;(time (length (tonari 11 3))) ; real 0.117 ; user 0.125 ; sys 0.000 792 gosh> (time (length (tonari 12 3))) ;(time (length (tonari 12 3))) ; real 1.292 ; user 1.279 ; sys 0.016 15374 gosh> (time (length (tonari 13 3))) ;(time (length (tonari 13 3))) ; real 17.527 ; user 17.691 ; sys 0.266 281434
n = 13 あたりからきついです。
d = 3 の場合、n < 9 は解なしで、n = 9 は解は 2 個。
n > 9 では n が 1 増える毎に、解の個数は約 20 倍、処理時間は約 10 倍ずつ増えます。
解となる順列数の増え方がヤバイですｗ
なお、n = 14 はメモリ不足でプログラムが落ちてしまいました。*1
巨大なリストを作ろうとするのがダメ*2です。予測では要素数が約 600 万個ぐらいのリストになるはずです。
答えは逐次表示してリストを持たないようにすれば良いのですが、
それでは LISP らしくないのでやる気が出ませんね。
n = 13 ぐらいまで求まれば良いよね（投げやり
