Project Euler Problem 24
0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?
順列とはモノの順番付きの並びのことである. たとえば, 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万番目はいくつか?
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: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?
考え方
0,1,2,3 の順列の場合| 何番目 | ÷ 3! | 剰余 | 剰余 ÷ 2! | 剰余 | |
|---|---|---|---|---|---|
| 0123 | 1 | 1 / 6 = 0 | 1 % 6 = 1 | 1 / 2 = 0 | 1 % 2 = 1 |
| 0132 | 2 | 2 / 6 = 0 | 2 % 6 = 2 | 2 / 2 = 1 | 2 % 2 = 0 |
| 0213 | 3 | 3 / 6 = 0 | 3 % 6 = 3 | 3 / 2 = 1 | 3 % 2 = 1 |
| 0231 | 4 | 4 / 6 = 0 | 4 % 6 = 4 | 4 / 2 = 2 | 4 % 2 = 0 |
| 0312 | 5 | 5 / 6 = 0 | 5 % 6 = 5 | 5 / 2 = 2 | 5 % 2 = 1 |
| 0321 | 6 | 6 / 6 = 1 | 6 % 6 = 0 | 0 / 2 = 0 | 0 % 2 = 0 |
| 1023 | 7 | 7 / 6 = 1 | 7 % 6 = 1 | 1 / 2 = 0 | 1 % 2 = 1 |
| 1032 | 8 | 8 / 6 = 1 | 8 % 6 = 2 | 2 / 2 = 1 | 2 % 2 = 0 |
| 1320 | 12 | 12 / 6 = 2 | 12 % 6 = 0 | 0 / 2 = 0 | 0 % 2 = 0 |
| 2013 | 13 | 13 / 6 = 2 | 13 % 6 = 1 | 1 / 2 = 0 | 1 % 2 = 1 |
b) 百の位は、千の位を除いた順列のうち、「(何番目 ÷ 3! の剰余) ÷ 2! の商 (ただし、剰余が 0 のときは -1)」番目の数字。(マイナスになったときは、順列の最後)
c) 十の位は、千の位、百の位を除いた順列のうち、(何番目 ÷ 3! の剰余) ÷ 2! の剰余が 0 なら 1番目の数字、1 なら 0番目の数字
d) 1の位は、残り
たとえば、６番目を求めたいときは、
a) 6番目 / 3! = 1。ただし、6番目 % 3! = 0 なので、1 - 1 = 0。0,1,2,3 のうちの 0番目 → "0"。
b) 剰余0 / 2! = 0。ただし、0剰余 % 2! = 0 なので、0 - 1 = -1。マイナスなので、1,2,3 のうちの 最後 → "3"。
c) 剰余0 % 2! = 0。1,2 のうちの 1番目 → "2"。
d) 残り → "1"。
７番目を求めたいときは、
a) 7番目 / 3! = 1。0,1,2,3 のうちの 1番目 → "1"。
b) 剰余1 / 2! = 0。1剰余 % 2! = 1 なのでそのまま。0,2,3 のうちの 0番目 → "0"。
c) 剰余1 % 2! = 0。2,3 のうちの 0番目 → "2"。
d) 残り → "3"。
