problem 24 - mtsuyuguの日記

0 から 9 までの数字の順列を辞書順に並べたとき、1000000 番目の数字は何か？という問題。確率統計にありがちな問題です。

pen and paper で

考えてたら紙と鉛筆で解いてしまった。

以下その時のメモ：

permutation-table:
9! = 362880
8! =  40320
7! =   5040
6! =    720
5! =    120
4! =     24
3! =      6
2! =      2
1! =      1

1000000 / 362880 = 2 ... 274240 ; 0123456789 -> の 2 番目 -> 2
274240  / 40320  = 6 ... 32320  ; 013456789 -> の 6 番目 -> 7
32320  /  5040 = 6  ... 2080    ; 01345689 -> の 6 番目 -> 8
2080 / 720 = 2 ... 640          ; 0134569 -> の 2 番目 -> 3
640 / 120 = 5 ... 40            ; 014569 -> の 5 番目 -> 9
40 / 24 = 1 ... 16              ; 01456 -> の 1 番目 -> 1
16 / 6 = 2 ... 4                ; 0456 -> の 2 番目 -> 5
4 / 2 = 2 ... 0                 ; 046 -> の 1 番目(割り切れてるから) -> 4

例えば 10 進数を 16 進数に変換する場合は、16 の階乗で割った商を桁の数にして、あまりに対して同じ事をどんどん繰り返していけばいいんだけど、今回のように順列の場合は桁の重みが階乗の数になり(*1)、商をに対して割り当てる数(*2)も変わっていくということ。

これを scheme にする。

scheme で。

(use util.stream)
(use srfi-1)

(define (permutation n k)
  (fold * 1 (iota k n -1)))

(define (p24)
  (let loop ((n 1000000)
             (digit (iota 10 0)) ; '(0 1 2 3 4 5 6 7 8 9)
             (table (map (lambda (x) (permutation x x)) (iota 10 9 -1))) ; permutation-table
             (result '()))
    (if (= n 0)
      (fold (lambda (x y) (+ (* y 10) x)) 0
            (append (reverse result) (reverse digit))) ; 残った数字をくっつけて数に変換
      (let* ((divisor (car table))    ; *1
             (m (modulo n divisor))
             (d (list-ref digit (- (quotient n divisor) ; *2
                                   (if (= m 0) 1 0))))) ; 割り切れた場合はひとつ前の数字を選ぶ
        (loop m
              (delete d digit) ; 選ばれた数字は消していく
              (cdr table)
              (cons d result)))))) ; 先頭に付けていく

(display (p24))