오일러 프로젝트 24

어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다. 이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다. 0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다.

012,   021,   102,   120,   201,   210…

0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까?

http://euler.synap.co.kr/prob_detail.php?id=24

접근

순열을 구하는 제너레이터를 만들어서 사용하거나, itertools.permutations() 와 같은 함수를 사용하면 모든 순열을 얻을 수 있지만, 이 방법을 사용하면 1백만번째 순열을 구하기 위해서 반복문을 백만번 돌려야 한다는 함정이 있다. 다른 방법으로 빠르게 구할 수 있는지를 알아보자. 방법이 있다면 N번째 순열을 구하는 함수를 작성할 수도 있을 것이다.

10개의 숫자는 너무 많으니까, 1, 2, 3, 4 의 네 개의 숫자의 모든 순열 중에서 15번째 순열이 무엇이 될지 생각해보자. 먼저 4개의 숫자로 만들 수 있는 모든 순열은 4! = 1 * 2 * 3 * 4 = 24개 이다. 이 중에서 1로 시작하는 것들은 1을 맨 앞자리에 고정하면 3!개가 된다는 것은 쉽게 생각할 수 있다. 즉 1로 시작하는 것이 6개, 2로 시작하는 것이 6개 이니, 15를 6으로 나눈 몫이 2이고 나머지가 3이니까, 15번째 순열은 3으로 시작하는 것 중에서 6번째라는 것을 알 수 있다. 남은 1, 2, 4에 대해서도 같은 방법을 사용할 수 있다. 31, 32, 34로 시작하는 순열은 각각 2개씩 있으므로 3을 2로 나눈 몫은 1이니 32로 시작하는 것 중에서 첫 번째 (나머지가 1)가 15번째 순열이 될 것이라는 것을 알 수 있다.

위 로직을 구현한 코드는 아래와 같다. 참고로 이 코드는 0부터 시작하기 때문에 문제의 답을 구하기 위해서는 999,999를 넘겨주어야 한다.

from functools import reduce
from typing import Sequence, TypeVar

T = TypeVar('T')

factorial = lambda n: reduce(lambda x, y: x * y, range(1, n+1), 1)

def pos_in_perm(n: int, xs: Sequence[T]) -> tuple[T, ...]:
    if n == 0:
        return (*xs,)
    l = len(xs)
    n = n % factorial(l)
    q, r = divmod(n, factorial(l -1))
    return (xs[q], *pos_in_perm(r, (*xs[:q], *xs[q+1:])))


print(''.join(str(c) for  c in pos_in_perm(999_999, range(10))))