오일러 프로젝트 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 번째 순열을 구하는 함수를 바로 작성해보도록 하자.
- n 개 요소 중에서 처음으로 한 개의 요소를 정하면, 그로부터 파생되는 가지수는 (n – 1)! 가지가 된다. 따라서 처음에 i 번째 요소가 오게 되면 이는 (n – i)! 번째 경우까지로 점프하고, (n – i)! + 1 번째 요소부터 시작된다고 볼 수 있다.
- 한 가지 요소가 결정되었다면 그 요소를 제외한 나머지 요소를 순열로 뽑아낼 수 있는데, 이 때 작은 순열의 a 번째 요소는 1.의 원리에 의해 (n – 1)! + a 번째 요소가 된다.
- 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