Original

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:

012 021 102 120 201 210

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

012 021 102 120 201 210
になる.

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

当てにならないソースコード(C#)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using System;
using System.Collections.Generic;

namespace ProjectEuler {
    class Problem24 : Problem{

        public Problem24() {
            string answer = "";
            List<int> stock = new List<int>{0,1,2,3,4,5,6,7,8,9},
                      result = new List<int>();
            // 開始インデックスが1ではなく0であるため、-1で辻褄を合わせる
            FindOrder(1000000-1, result, stock);
            result.ForEach((n) => answer += n.ToString());
            Console.WriteLine("> " + answer);
        }
       
        List<int> FindOrder(int target, List<int> result, List<int> stock) {
            int x = 0,
                p = Permutation(stock.Count-1);
            for (int i=0; i < stock.Count; i++, x+=p) {
                if (x + p > target) {
                    result.Add(stock[i]);
                    stock.RemoveAt(i);
                    return FindOrder(target - x, result, stock);
                }
            }
            return result;
        }

        public int Permutation(int n){
            return n > 1 ? n * Permutation(n - 1) : 1;
        }
    }
}


再帰で解けることに気づけば非常に簡単な問題です。