[Project Euler] Problem 24 「辞書式順列」

順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると次のようになる.

012 021 102 120 201 210

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?

力技で行きます.

1. 順列を求める.
2. 100万番目の要素を求める.

順列を求める過程でソートし, 辞書順になるようにしておきます. 手続きは次のようになります.

(require srfi/1)

;; リストから要素を一つ取り除く
(define (remove-one lst obj)
  (cond ((null? lst) ())
        ((equal? (car lst) obj) (cdr lst))
        (else (cons (car lst) (remove-one (cdr lst) obj)))))

;; 順列を求める
(define (permutation items)
  (if (null? items)
      '(())
      (apply append
             (map (lambda (item)
                    (map (lambda (p) (cons item p))
                         (permutation (remove-one items item))))
                  (sort items <)))))

(define ans (permutation '(0 1 2 3 4 5 6 7 8 9)))

計算します. メモリは２GB必要です.

ようこそ DrRacket, バージョン 5.3.3 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (list-ref ans 999999)
(2 7 8 3 9 1 5 4 6 0)
>