Chương trình tìm hoán vị thứ k theo thứ tự từ điển từ 1 đến n trong Python

Cho n và k. Xét danh sách [1, 2, ..., n] và tất cả các hoán vị theo thứ tự từ điển. Tìm hoán vị thứ k (1-indexed) dưới dạng chuỗi.

Ví dụ: n = 4, k = 5 → "1432" (hoán vị: 1234, 1243, 1324, 1342, 1423, 1432...).

Giải pháp

Sử dụng hệ số factorial (factoradic) để xác định trực tiếp hoán vị thứ k:

• Hàm factors(num): chuyển số k thành biểu diễn factorial (factoradic)
• Khởi tạo numbers = [1..n]
• Điền các chữ số đầu tiên của kết quả bằng cách pop(0) từ numbers cho đến khi độ dài factoradic bằng độ dài numbers
• Với mỗi chỉ số trong factoradic, pop phần tử tại chỉ số đó từ numbers và nối vào kết quả

Ví dụ minh họa

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))

Đầu vào

4, 5

Đầu ra

1432