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이 선택된다. 이와 같은 방식을 구현한다.

# -*- 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이다.