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 factorialdef 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 mainimport ( "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