Lexicographic Permutations
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012, 021, 102, 120, 201, 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째를 구하는 문제다.
내가 처음으로 생각한 구현 방식은 다음과 같다.
- 다중 반복문을 통해 모든 순열을 구해
list로 만들어 준다. list[999999]를 출력한다.
하지만 이렇게 구현한다면 반복문을 9중으로 사용해야한다. 다른 방법을 생각해보자...
그냥 앞에서 부터 1자리 씩 맞춰나가는 방법은 어떨까?
예를 들어서 첫 숫자가 0인 경우는 이다. 우리는 1,000,000번째 숫자를 구해야하니 첫 숫자는 0보다 클 것이다. 이런 방식을 반복한다면 1000000 // 9! = 2가 첫 번째 숫자임을 알 수 있고
1000000 % 9! = 274240을 다음 타겟으로 지정하고 2를 뺀 9개의 숫자 중에 1개를 고정하며 같은 과정을 반복해주면 모든 숫자를 구할 수 있을 것이다. 그렇다면 구현 방식은 다음과 같을 것이다.
- n 팩토리얼을 구현해주는 함수를 작성.
- 반복문을 통해 n번째 순열을 구해주는 함수를 작성.
팩토리얼 함수는 이전에 구현해본 적이 있으니 한번에 작성해보자.
def factorial(n):
result = 1;
for i in range (n):
result *= i + 1
return result
def nth_permutation(n):
target = n
digits = list(range(10))
result = []
# 9부터 0까지 1씩 줄여나간다.
for i in range(len(digits) - 1, -1, -1):
factor = factorial(i)
index = target // factor
result.append(digits.pop(index)) # 고른 숫자는 빼야하니
target = target % factor
return ''.join(map(str, result)) # result의 값을 str으로 변환 후 join
print(nth_permutation(999999))
>>> 2783915460 # correct그리고 python의 itertools 모듈을 활용한다면 더 간단하게 구현이 가능하다.
from itertools import permutations
# 0~9까지 모든 사전식 순열을 만들어준다
digits = '0123456789'
all_permutations = sorted(permutations(digits))
# 1,000,000 째 숫자를 조합해서 출력한다,
millionth_permutation = ''.join(all_permutations[999999])
print(millionth_permutation)
>>> 2783915460실무에서는 이 방식을 사용하도록 하자.
오늘은 여기까지
-2025.01.13-
