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! 剰余
012311 / 6 = 01 % 6 = 11 / 2 = 01 % 2 = 1
013222 / 6 = 02 % 6 = 22 / 2 = 12 % 2 = 0
021333 / 6 = 03 % 6 = 33 / 2 = 13 % 2 = 1
023144 / 6 = 04 % 6 = 44 / 2 = 24 % 2 = 0
031255 / 6 = 05 % 6 = 55 / 2 = 25 % 2 = 1
032166 / 6 = 16 % 6 = 00 / 2 = 00 % 2 = 0
102377 / 6 = 17 % 6 = 11 / 2 = 01 % 2 = 1
103288 / 6 = 18 % 6 = 22 / 2 = 12 % 2 = 0
13201212 / 6 = 212 % 6 = 00 / 2 = 00 % 2 = 0
20131313 / 6 = 213 % 6 = 11 / 2 = 01 % 2 = 1
a) 千の位は、「何番目 ÷ 3! の商 (ただし、剰余が 0 のときは -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 = ()

C

C++

C++Builder

VC++

C#

Java

Objective-C

D

VB

VB.NET

Delphi

Ada

PL/SQL

T-SQL

関数型

inserted by FC2 system