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