โปรแกรมหาลำดับการเรียงสับเปลี่ยน lexicographic ลำดับที่ k จาก 1 ถึง n ใน Python

คำอธิบายโจทย์

ให้ค่า n และ k พิจารณาการเรียงสับเปลี่ยน (permutation) ของ [1, 2, ..., n] ตามลำดับ lexicographic หาลำดับที่ k (1-indexed) เป็นสตริง

ตัวอย่าง

n = 4, k = 5 → เอาต์พุต: "1432" (ลำดับที่ 5 ของ 1234, 1243, 1324, 1342, 1432, ...)

วิธีแก้ปัญหา

ใช้ Factorial Number System (Factoradic):

แปลง k เป็นเลขฐาน factorial (factoradic representation)
factoradic บอกว่าแต่ละตำแหน่งควรเลือกตัวที่กี่จากตัวเลขที่เหลือ
สร้างผลลัพธ์โดยเลือกและนำออกจาก list ตาม index จาก factoradic

โค้ด Python

from collections import deque

def factors(num):
    quo = num
    res = deque([0])
    i = 2
    while quo:
        quo, rem = divmod(quo, i)
        res.appendleft(rem)
        i += 1
    return res

class Solution:
    def solve(self, n, k):
        numbers = [num for num in range(1, n + 1)]
        res = ""
        k_fact = factors(k)
        while len(k_fact) < len(numbers):
            res += str(numbers.pop(0))
        for index in k_fact:
            number = numbers.pop(index)
            res += str(number)
        return res

ob = Solution()
n = 4
k = 5
print(ob.solve(n, k))

อินพุต

4, 5