Problem 41 - Pandigitalな素数

50問達成。

n桁の数がPandigitalであるとは, 1からnまでの数を各桁に1つずつもつことである. 例えば2143は4桁のPandigital数であり, かつ素数である.
n桁のPandigitalな素数の中で最大の数を答えよ.

ハイ。組合せ。しかも、スゲー大量の検索量が必要。

まだ、無限リストをうまく使えないので、Problem24のようにn番目の組合せは何かという感じで求めてみた。

(define (list->number l)
  (letrec ((iter (lambda (l cont)
                  (if (null? l)
                      (cont 0 0)
                      (iter (cdr l) (lambda (sum k)
                                      (cont (+ (* (car l) (expt 10 k)) sum)
                                            (+ k 1))))))))
          (iter l (lambda (sum k) sum))))

(define (prime? n)
  (letrec ((trial-divisor
             (lambda (t)
               (or (< n (* t t))
                   (and (not (zero? (remainder n t)))
                        (trial-divisor (+ t 2)))))))
    (and (> n 1)
         (or (= n 2)
             (and (odd? n)
                  (trial-divisor 3))))))

(define (remove-ref l n cont)
  (if (zero? n)
      (cont (car l) (cdr l))
      (remove-ref (cdr l)
                  (- n 1)
                  (lambda (rm m)
                    (cont rm (cons (car l) m))))))

(define (problem41)
  (letrec ((fact (lambda (n) (apply * (iota n 1))))
           (permutation
             (lambda (n fac i l)
               (if (= i 0)
                   l
                   (remove-ref l
                               (quotient n fac)
                               (lambda (rm res)
                                 (cons rm
                                       (permutation (modulo n fac)
                                                    (if (zero? i) 0 (quotient fac i))
                                                    (- i 1)
                                                    res)))))))
           (calc (lambda (n fac len l)
                   (list->number (permutation n fac (- len 1) l))))
           (try (lambda (n fac len l)
                  (cond ((negative? n) #f)
                        ((prime? (calc n fac len l))
                         (calc n fac len l))
                        (else (try (- n 1) fac len l)))))
           (iter (lambda (n)
                   (let ((res (try (- (fact n) 1)
                                   (fact (- n 1))
                                   n
                                   (iota n 1))))
                     (or res (iter (- n 1)))))))
    (iter 9)))


(problem41) ; 7652413

(time (problem41)) ; cpu time: 4919 real time: 4919 gc time: 1880

だいぶ書き直した。倍以上は早くなった。

改善ポイントは、

remove-refを多値にして消した値と残りを返せるようにした。
階乗の計算をなるべく前で済ませるようにして無駄な計算を減らす。

前よりはマシな感じ。