順列を求める(個数だけ) その後

寝不足のまま続きを考えましたｗ

  (define (iter-3 ans rests rests1 count)
    (if (null? rests)
        count
        (iter-3 ans
                (cdr rests)
                rests1
                (let ((x (car rests)))
                  (+ count (iter-2 (append ans (cons x nil)) x (remove x rests1)))))))

  (define (iter-2 ans num rests)
    (if (null? rests)
	(if (check ans)
            1
	    0)
	(if (not (check ans))
	    0
            (iter-3 ans rests rests 0))))

直した部分だけ。
map をやめてリストを作らなくしただけです。
iter-3 の rests はイテレーション用に使うため破壊されてしまうので、
破壊されない rests1 (名前適当) を用意して、
(remove x rests1) として iter-2 の第三引数に渡すのがポイントです。
眠かったため実装は苦労しましたｗｗｗ

処理時間を計測してみます。

gosh> (time (tonari 10 3))
;(time (tonari 10 3))
; real   0.016
; user   0.016
; sys    0.000
40
gosh> (time (tonari 11 3))
;(time (tonari 11 3))
; real   0.109
; user   0.109
; sys    0.000
792
gosh> (time (tonari 12 3))
;(time (tonari 12 3))
; real   1.186
; user   1.248
; sys    0.094
15374
gosh> (time (tonari 13 3))
;(time (tonari 13 3))
; real  15.600
; user  16.911
; sys    0.562
281434
gosh> (time (tonari 14 3))
;(time (tonari 14 3))
; real 237.042
; user 249.180
; sys   11.856
5089060

ほんの少しですが処理時間は改善しましたかね？

もっと速く解くには C/C++*1 とかで書くしか無いです。
1/50 倍ぐらいには短縮できます。たぶん。
C++ コンパイラは優秀ですから爆速です。

インタプリタ言語ではこのぐらいが限界ですかね(眠

*1:C で書く場合でもC++コンパイラの使用をおすすめします。クラスなんてまったく使わなくても C++ コンパイラを使うのはとても有益です。「今日から C 言語始めたんだけど・・・」という人でも堂々と C++ コンパイラを使ってください。クラスなんて書く必要はありません。