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?

Solution p24.py 1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

from math import factorial

def get_perm (digits, number) :

if len(digits) == 0 :

return ''

(perm, counter) = ('' , factorial(len(digits) - 1 ))

for digit in digits:

if counter >= number:

digits.remove(digit)

perm += str(digit) + get_perm(digits, number)

break

number -= counter

return perm

if __name__ == '__main__' :

import time

startTime = time.time()

perm = get_perm([d for d in range(10 )], 1000000 )

print perm, '%sms' % ((time.time() - startTime) * 1000 )

p24.php 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

<?php

function factorial ($n) {

$result = 1 ;

for ($i = 2 ;$i <= $n;$i++) $result*= $i;

return $result;

}

function get_perm ($digits, $number) {

$perm = "" ;

$length = count($digits);

$counter = factorial($length - 1 );

for ($i = 0 ;$i < $length;$i++) {

if ($counter >= $number) {

$segment = array_splice($digits, $i, 1 );

$perm = $segment[0 ] . get_perm($digits, $number);

break ;

}

$number-= $counter;

}

return $perm;

}

$startTime = microtime(true );

$digits = array (0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 );

$perm = get_perm($digits, 1000000 );

$costs = (microtime(true ) - $startTime) * 1000 ;

echo "$perm ${costs}ms\n" ;

?>

p24.go 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

35

36

37

package main

import (

"fmt"

"strconv"

"time"

)

func factorial (n int ) int {

result := 1

for i := 2 ; i <= n; i++ {

result *= i

}

return result

}

func get_perm (digits []int , number int ) string {

perm, length := "" , len (digits)

counter := factorial(length - 1 )

for i := 0 ; i < length; i++ {

if counter >= number {

digit := digits[i]

digits = append (digits[:i], digits[i+1 :]...)

perm += strconv.Itoa(digit) + get_perm(digits, number)

break

}

number -= counter

}

return perm

}

func main () {

startTime := time.Now()

digits := []int {0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }

perm := get_perm(digits, 1000000 )

fmt.Println(perm, time.Now().Sub(startTime))

}

I’m the 57181st person to have solved this problem.

I’ve just advanced to Level 1. 61264 members (15.9%) have made it this far.

I have earned 1 new award:

The Journey Begins: Progress to Level 1 by solving twenty-five problems