home
>
Project Euler
>
ForNext
Shut the fuck up and write some code
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の位は、残り
たとえば、6番目を求めたいときは、
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"。
7番目を求めたいときは、
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"。
VBScript
JScript
Perl
PHP
Python
Ruby
PowerShell
Scala
更新日 : 2013.02.12
まづ、0,1,2,3 の数列で試してみる
scala> def problem24(x:Int) = { | var i = x | var s = (0 to 3).toSet | (3 to 1 by -1).foreach{n => | //println(n) | val j = if (n == 1) 1 else (n to 2 by -1).reduceLeft(_*_) | var k = i / j | i = i % j | if (i == 0) k = k - 1 | if (k < 0) k = n + 1 + k | val m = s.toList(k) | print(m) | s = s - m | if (n == 1) println(s.toList(0)) | } | } problem24: (x: Int)Unit scala> (1 to 13).foreach(problem24) 0123 0132 0213 0231 0312 0321 1023 1032 1203 1230 1302 1320 2013
0,1,2,3,4,5,6,7,8,9 の 1000000番目
scala> def problem24(x:Int) = { | var i = x | var s = (0 to 9).toSet | (9 to 1 by -1).foreach{n => | //println(n) | val j = if (n == 1) 1 else (n to 2 by -1).reduceLeft(_*_) | var k = i / j | i = i % j | if (i == 0) k = k - 1 | if (k < 0) k = n + 1 + k | val m = s.toList.sorted.toList(k) | print(m) | s = s - m | if (n == 1) println(s.toList(0)) | } | } problem24: (x: Int)Unit scala> (999999 to 1000001).foreach(problem24) 2783915406 2783915460 2783915604
最後は...
scala> problem24((1 to 10).product) 9876543210
F#
更新日 : 2013.02.10
まづ、0,1,2,3 の数列で試してみる
> let problem24 x = - let i = ref x - let s = ref (Set [0..3]) - [3 .. -1 .. 1] - |> List.iter - ( - fun n -> - let j = if n = 1 then 1 else List.reduce(*) [n .. -1 .. 2] - let mutable k = !i / j - i := !i % j - if !i = 0 then k <- k - 1 - if k < 0 then k <- n + 1 + k - let m = (!s |> Set.toArray).[k] - printf "%d" m - - s := !s |> Set.remove m - if n = 1 then - printfn "%d" (!s |> Set.toArray).[0] - ) - ;; val problem24 : int -> unit > [1..13] |> List.iter(problem24) - ;; 0123 0132 0213 0231 0312 0321 1023 1032 1203 1230 1302 1320 2013 val it : unit = ()
0,1,2,3,4,5,6,7,8,9 の 1000000番目
> let problem24 x = - let i = ref x - let s = ref (Set [0..9]) - [9 .. -1 .. 1] - |> List.iter - ( - fun n -> - let j = if n = 1 then 1 else List.reduce(*) [n .. -1 .. 2] - let mutable k = !i / j - i := !i % j - if !i = 0 then k <- k - 1 - if k < 0 then k <- n + 1 + k - let m = (!s |> Set.toArray).[k] - printf "%d" m - - s := !s |> Set.remove m - if n = 1 then - printfn "%d" (!s |> Set.toArray).[0] - ) - ;; val problem24 : int -> unit > [999999..1000001] |> List.iter(problem24) - ;; 2783915406 2783915460 2783915604 val it : unit = ()
最後は...
> problem24 (List.reduce(*) [10 .. -1 .. 1]);; 9876543210 val it : unit = ()