ホーム - Project Euler

Problem 24¶

Lexicographic Permutations¶

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

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

辞書式順列¶

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

になる.

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

(import (scheme base)
        (gauche base))

(define (my-permutation lis)
  (let perm-sub ([rest lis] [sub '()] [result '()])
    (if (null? rest)
      (cons (reverse sub) result)
      (fold-right (^[n result]
                    (perm-sub (delete n rest) (cons n sub) result))
                  result
                  rest))))

(define answer-24
  (list-ref (my-permutation (iota 10)) 99_9999))

(format #t "24: ~d~%" answer-24)