프로젝트 오일러 024

문제

24번 문제

0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은?

사이냅소프트

접근

이미 모든 순열을 생성하는 제너레이터를 어떻게 구현하는 지는 한 번 소개한 바 있습니다. 이 문제에서는 1,000,000 번이나 반복해야 하지만, 놀랍게도 '참아줄 법한' 수행시간이 나옵니다. itertools 모듈의 경우에는 아주 빠르기 때문에 어렵지 않게 답을 구할 수 있습니다.

from itertools import permutations

def main():
  s = tuple('0123456789')
  for (i, x) in enumerate(permutations(s)):
    if  i == 999_999:
      print(''.join(x))
      return

main()

enumerate()의 인덱스는 0부터 시작하니, 백만번째 순열은 인덱스가 999,999일 때라는 점만 주의하면 됩니다.

백만번째 순열을 한 번에 찾기

N번째 순열을 찾는 다른 방법을 살펴보겠습니다. 0으로 시작하는 모든 순열들은 9! 개가 됩니다. 100만을 9!로 나누면 몫은 2, 나머지는 274,240입니다. 즉 0, 1로 시작하는 모든 순열은 지났다는 의미입니다. 따라서 첫번째 숫자는 2입니다. 남은 274,240에서는 다시 남은 숫자들 중 1개를 정하면 각각 8!의 순열이 있습니다. 나눠보면 몫은6, 나머지는 32,320입니다. 즉 3, 4, 5, 6, 7, 8 은 지나고 두 번째 숫자는 9로 결정됩니다. 이런 식으로 하나씩 찾아보면 100만번째 순열은 구할 수 있습니다. 이 방법은 목표한 순서의 순열만 찾으므로 1천만이나, 10억번째 순열도 빠르게 찾을 수 있습니다.

이를 조금 일반화한 알고리듬은 아래와 같습니다. (팩토리얼 함수는 간단히 구현할 수 있으니 생략합니다.)

def nth_perm(xs, n):
  if n == 0:
    return (*xs)
  l = len(xs)
  n = n % (factorial(l))
  q, r = divmod(n, factorial(l -1))
  return (xs[q], *nth_perm(r, (*xs[:q], *xs[q+1:])))

print(''.join(nth_perm(tuple('0123456789'), 100_0000)))