"""
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 time
from itertools import permutations


def timer(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        print(f"Execution time: {end_time - start_time:.6f} seconds")
        return result

    return wrapper


def ordered_permutations(n: int) -> list[int]:
    digits = list(range(10))
    all_permutations = permutations(digits)
    for _ in range(n - 1):
        next(all_permutations)
    return next(all_permutations)


@timer
def main_iter():
    n = 1000000
    result = ordered_permutations(n)
    print(f"used iter: {''.join(map(str, result))}")


def get_permutation(seq, k):
    """
    返回序列 seq 的第 k 个字典序排列 (1-based)

    参数:
        seq: 可迭代对象（列表、元组、字符串等），元素需有序
        k: 第 k 个排列（从1开始计数）

    返回:
        与输入类型相同的排列结果
    """
    n = len(seq)

    # 预计算阶乘
    factorial = [1]
    for i in range(1, n):
        factorial.append(factorial[-1] * i)

    # 将输入转为列表（复制一份避免修改原序列）
    elements = list(seq)
    k -= 1  # 转为0-based索引

    # 构建结果
    result = []
    for i in range(n, 0, -1):
        index = k // factorial[i - 1]  # 当前位选择的元素索引
        result.append(elements.pop(index))
        k %= factorial[i - 1]  # 更新剩余位

    # 根据输入类型返回相应格式
    if isinstance(seq, str):
        return "".join(result)
    return result


@timer
def main_math():
    n = 1000000
    result = get_permutation("0123456789", n)
    print(f"used math: {result}")


if __name__ == "__main__":
    main_iter()
    main_math()