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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #!/usr/bin/python2
# -*- coding: utf-8 -*-
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)
|
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";
?>
|
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