[Project Euler]24. 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?

 

[풀이]
def factorial(n):
    if n==1:
        return 1
    else:
        return n*factorial(n-1)

def isEven(n):
    if n%2==0:
        return True
    else:
        return False

pList = list(range(0,10))
idx = 1000000
lenList = len(pList)
result = []

for i in range(1, lenList-1):
    fac = factorial(lenList-i)
    if fac==2 and isEven(idx):
        result.append(pList.pop((idx//fac)-1))
    else:
        result.append((pList.pop(idx//fac)))
    idx = idx%fac

if isEven(idx):
    result.extend([pList.pop(1),pList.pop(0)])
else:
    result.extend([pList.pop(0),pList.pop(0)])

print(result)

 

'''
우선 순열은 자리수에 따라서 n!가지 경우를 가질 수 있기 때문에 factorial 함수를 만들어줬다.

isEven 함수를 만든 것은 idx가 짝수인지 홀수인지에 따라 구하는 계산이 달라지기 때문이다.

맨 앞자리 수의 인덱스는 idx를 n-1!으로 나눈 값의 몫이다.
인덱스를 지정하여 pList에서 pop하도록 했다.(순열에서는 한 번 사용한 수는 두번 사용할 수 없기 때문에)

사이 수는 일련의 계산과정을 통해 뽑아오도록했고.. (이게 생각해낼때도 복잡했는데 막상 설명하려니 머리가 꼬인다...)

그리고 맨 마지막 두 자리의 인덱스는 10, 00으로 고정되었다.
짝수인 경우는 10, 홀수인 경우는 00
맨 마지막 자리가 0인덱스인것은 당연하다.. pList에는 한 가지 값만 남았기 때문!

생각보다 잘 정리된 것 같진 않은데.. 
그래도 혼자 힘으로 문제해결을 한 것이 뿌듯하다!!

'''