오일러 프로젝트 24

오일러 프로젝트 24 번은 숫자 10개(0~9)로 만들어지는 순열 중에서 백만번째 항을 구하는 문제이다.

어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 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 함수를 이용하면 특정 원소들로부터 n개짜리 순열을 생성하는 생성자를 얻을 수 있다. 그런데 문제에서는 100만번째 항을 구해야 하므로 이 생성자를 이용한다 하더라도 next() 를 백만번 호출해야 하는 부담이 있다. 따라서 n 개 요소를 사용한 순열에서 m 번째 순열을 구하는 함수를 바로 작성해보도록 하자.

  1. n 개 요소 중에서 처음으로 한 개의 요소를 정하면, 그로부터 파생되는 가지수는 (n – 1)! 가지가 된다. 따라서 처음에 i 번째 요소가 오게 되면 이는 (n – i)! 번째 경우까지로 점프하고, (n – i)! + 1 번째 요소부터 시작된다고 볼 수 있다.
  2. 한 가지 요소가 결정되었다면 그 요소를 제외한 나머지 요소를 순열로 뽑아낼 수 있는데, 이 때 작은 순열의 a 번째 요소는 1.의 원리에 의해 (n – 1)! + a 번째 요소가 된다.
  3. 1., 2.의 성질을 이용하여 잔여 개수의 팩토리얼 값을 이용해서 몇 번째까지 원소를 정할 것인지를 알 수 있고, 이것이 남은 원소가 없을 때까지 반복하면 정해진 순서의 순열을 구할 수 있다.

로직 자체가 말로 풀어써서 이해가 잘 안될 수 있는데, 간단하게 파이썬 코드를 보면서 설명하겠다.

## 먼저 팩토리얼 계산을 위한 함수를 만든다.
from functools import reduce

def factorial(n):
  if n < 2:
    return 1
  return reduce(lambda x,y:x*y, range(1, n+1))

def perms(n, ls):
  """리스트 ls로부터 n번째 순열인 리스트를 찾는다. n = 0, 1, 2, ... """
  if n == 0: 
    return ls
  l = len(ls)
  ## 만약 n번째...라는게 가용한 순열 가지수보다 크면 다시 처음부터 순열을 만든 것으로 되돌아서
  ## 계산한다. 
  n = n % factorial(l)
  ## 1개를 제외하고 남은 요소의 팩토리얼만큼을 n으로 나눈 몫은 이번 순열에서 맨 앞에 오는 요소가
  ## 몇 번째 요소인지를 정하게 된다. 
  q, r = divmod(n, factorial(l-1))
  ## 이제 첫번째 원소가 정해졌으니, 나머지를 가지고 다시 순열을 찾는다.
  return [ls[q]] + perms(r, ls[:q]+ls[q+1:])

def e24():
    print("".join(perms(999999, list('0123456789'))))

%time e24()

#2783915460
#Wall time: 0 ns

알고리듬 자체가 매우 간단하기 때문에 Swift 코드도 단순하게 쓰여진다.

func permutation<A>(at n:Int, of xs: [A]) -> [A] {
  func factroial(_ x: Int) -> Int {
    guard x > 1 else { return 1 }
    return (2...x).reduce(1, *)
  }
  let n = n % factorial(xs.count)
  var xs = xs
  let l2 = factorial(xs.count - 1)
  let q, r = (n / l2, n % l2)
  let a = xs.remove(at: q)
  return [a] + permutation(at: r, of: xs)
}

print(permutation(at:999_999, of:Array(0...9))
       .map{ String($0) }.joined(separator:""))
## 2783915460