Project Euler - Problem 24

問題

• 原文

  What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

• 日本語訳

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

解答

n (> 0)桁目の数字が決まると残りの数字の順列は(n - 1)!通りですから、一般にn桁の順列の（0から数えて）m番目というとき、m = p_n(n - 1)! + p_n-1(n - 2)! + ... + p₁(0)! (0 <= p_i < i)と表すと、p_n, p_n-1, ..., p₁の値は一意に定まります。 よってn桁目の数字を決めるとき、その時点で使える数字を昇順に並べた中からp_n番目の数字を選ぶという操作をn = 1まで繰り返すことで解が得られます。

(use srfi-1)

(define (factorial n) (apply * (iota n 1)))

(define (solve)
  (define (solve-1 n digits acc)
    (if (null? digits) (list->string (map integer->digit (reverse acc)))
        (let* ((fact (factorial (- (length digits) 1)))
               (mult (floor (/ n fact)))
               (digit (ref digits mult))
               (rest (remove (cut = digit <>) digits)))
          (solve-1 (- n (* fact mult)) rest (cons digit acc)))))
  (solve-1 (- 1000000 1) (iota 10) '()))

(define (main argv)
  (display (solve))
  (newline))