24. Lexicographic permutations

1. 개요

문제는 이곳에서 확인할 수 있다. 숫자 0, 1 그리고 2가 주어졌다고 하자. 이 숫자들로 만들 수 있는 순열을 크기 순으로 나열하면 012, 021, 102, 120, 201 그리고 210이다. 이때 이 순열의 3번째 값은 102이다. 이와 같은 방식으로 0부터 9까지의 숫자가 주어졌을 때 100만번째 값을 구하는 것이 목표이다.

2. 구현: ver 1.0

0, 1, 2가 주어지고 5번째 값을 구한다고 하자. 가장 앞에 오는 수는 2이다. 왜냐하면 0과 1이 가장 앞에 올때 순열의 가짓수는 각각 2이기 때문이다. 이후 남은 5-2-2=1번째 순열을 구하면 되므로 남은 0과 1이 선택된다. 이와 같은 방식을 구현한다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

# -*- coding: utf-8 -*- import math as m   digit_list = range(0, 10) digit_length = len(digit_list) target_index = 1000000 result = '' idx = 0   while digit_list:       while m.factorial(digit_length-1) < target_index:         target_index -= m.factorial(digit_length-1)         idx += 1     else:         result += str(digit_list.pop(idx))         idx = 0         digit_length -= 1   print(result)

답은 2783915460이다.