Problem 24 - 順列(2)

前回の教訓を元に攻めていく。

Problem 24 - PukiWiki

順列とはモノの順番付きの並びのことである. たとえば, 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万番目を答えよ

3桁での結果はこう。

(permutations (iota 3)) ; ((0 1 2) (0 2 1) (1 0 2) (1 2 0) (2 0 1) (2 1 0))

3! = 6個の組み合わせがある。

この中で、4番目の(1 2 0)を選んでみよう。

(define (fact n) (apply * (iota n 1)))
(define (selector i n)
  (if (= n 1)
      '()
      (cons (quotient i (fact (- n 1)))
            (selector (modulo i (fact (- n 1))) (- n 1)))))

(selector (- 4 1) 3) ; (1 1)
  • '(0 1 2)から1番目の1を選んで
  • '(0 2)から1番目の2を選んで
  • '(0)残りのゼロを選択。

(1 2 0)というリストを選んだ事がわかる。

これを元に、10個の順列から、100万番目を選んでみる。

(selector (- 1000000 1) 10) ; (2 6 6 2 5 1 2 1 1)

10!かかっていた計算が、10回で済む。

選択したインデクス番号だけで、何を選んだのかのかわからないので、紐づけを追加してっと。

(define (problem24 i n)
  (define (fact n) (apply * (iota n 1)))
  (define (selector i n)
    (if (= n 1)
        '()
        (cons (quotient i (fact (- n 1)))
              (selector (modulo i (fact (- n 1))) (- n 1)))))
  (define (remove-ref l k)
    (if (= k 0)
        (cdr l)
        (cons (car l)
              (remove-ref (cdr l) (- k 1)))))
  (define (iter src l)
    (if (null? l)
        src
        (cons (list-ref src (car l))
              (iter (remove-ref src (car l)) (cdr l)))))
  (iter (iota n) (selector i n)))

(problem24 (- 1000000 1) 10) ; (2 7 8 3 9 1 5 4 6 0)

いぇい。

ついでに

リストを数値に変換するユーティリティ。

(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))))

(list->number '(2 7 8 3 9 1 5 4 6 0)) ; 2783915460

継続で多値。