Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|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:

<div style="text-align:center">012 021 102 120 201 210</div>

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の順列を辞書順に並べると

<div style="text-align:center">012 021 102 120 201 210</div>

になる.

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

```scheme

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

```