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?
순열은 객체의 정렬된 배열이다. 예를 들어, 3124는 1,2,3,4로 만들 수 있는 순열 중 하나이다. 모든 순열이 수치나 알파벳으로 나열되어 있으면 사전 순서(lexicographic order)라 부른다. 0,1,2의 사전 순열은 다음과 같다.
012 021 102 120 201 210
0,1,2,3,4,5,6,7,8,9의 백만번째 사전 순열은 무엇인가?
--------------------------------------------------------------------------
조금 머리를 쓰면 계산에 의해 풀수도 있을 것 같긴 했는데, 0123456789로 순열을 구해서 100만째 것을 찾는 단순한 방법으로 해결했다.
실제 조금만 머리를 쓰면 각 자리수를 바꾸는 조합은 순열이므로 팩토리얼(!)로 구할 수 있고, 첫자리가 0으로 시작되는 경우 가능한 순열은 9!=362880번 있으며, 이를 적용하면 2로 시작되는 순열이 되는 것임을 알 수 있다. 이러한 방식으로 백만에서 숫자를 빼 나간다면 해당하는 순열의 숫자를 좀 더 빠른 시간내에 찾을 수 있겠지만 단순하게 구현 가능해서 실제로 코드를 작성해 보지는 않았다.