[Project Euler] Problem 24

원문: Problem 24

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의 가능한 수열 중 하나이다. 만약, 수열의 모두가 숫자 순서로 또는 알파벳 순서로 나열되어 있다면, 그것을 사전 상의 순서라고 한다. 0, 1 과 2의 사전 상의 수열은 다음과 같다:

012 021 102 120 201 210

숫자 0, 1, 2, 3, 4, 5, 6, 7, 8, 그리고 9의 사전 상의 수열 중 백만 번째는 무엇인가?

오랫만에 계산하는 것이 더 빠른 문제가 나왔다. 뭐, 가능하다면 더 빠르게 코딩할 수도 있겠지만 그래도 막상 해보니 복잡했다...

Python

#!/usr/bin/evn python3
Str = ''
n = 0 

def permutation(number):
    global Str, n
    for i in range(number):
        if str(i) not in Str:
            Str += str(i)
            if permutation(number):
                return True
    if len(Str) == number:
        n += 1
    if n == 1000000:
        return True
    Str = Str[:-1]

permutation(10)
print(Str)

접기