[Euler Project] Problem 24 using Python

Euler Project 24번 문제는 permutation이라는 logic 자체가 작은 문제들로 나눠서 풀 수 있는 문제다.

따라서 제귀적으로 앞 자리부터 하나의 digit씩 찾아가면 문제의 답을 찾을 수 있다.

 

 

"""
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?
"""

import numpy as np
import math

# find first digit and redundant index
def get_digit(target_idx, digit_nums):
    digit = target_idx // math.factorial(digit_nums-1)
    redundant = target_idx - math.factorial(digit_nums-1) * digit

    return digit, redundant

if __name__ == '__main__':
    # 0: first >> 999999: millionth
    target_idx = 999999
    digit_num = 10
    digits = [x for x in range(digit_num)]

    res = []
    for i in range(digit_num):
        digit, red = get_digit(target_idx, 10-i)
        print(digit, red)

        # append given digit
        res.append(str(digits[digit]))
        # remove the number just picked
        digits.remove(digits[digit])
        # update target idx
        target_idx = red

    answer = int(''.join(res))
    print(answer)