Tìm hoán vị thứ n theo thứ tự từ điển của chuỗi trong Python

Cho chuỗi độ dài m chỉ chứa chữ thường, tìm hoán vị thứ n theo thứ tự từ điển (lexicographically).

Ví dụ: chuỗi = "pqr", n = 3 → Kết quả: "qpr" vì các hoán vị theo thứ tự: [pqr, prq, qpr, qrp, rpq, rqp].

Thuật toán

1. Tính trước giai thừa đến 20!.
2. Đếm tần suất từng ký tự.
3. Xây dựng kết quả ký tự bởi ký tự: thử đặt từng ký tự có sẵn, tính số hoán vị có thể tạo được với phần còn lại. Nếu đủ ≥ n, chọn ký tự đó; trừ n và tiếp tục.
4. Cuối cùng nối các ký tự còn lại theo thứ tự giảm dần.

Ví dụ code

MAX_CHAR = 26
MAX_FACT = 20
factorials = [None] * MAX_FACT

def get_nth_permute(string, n):
    factorials[0] = 1
    for i in range(1, MAX_FACT):
        factorials[i] = factorials[i - 1] * i
    size = len(string)
    occurrence = [0] * MAX_CHAR
    for i in range(size):
        occurrence[ord(string[i]) - ord('a')] += 1
    res = [None] * MAX_CHAR
    Sum = 0
    k = 0
    while Sum != n:
        Sum = 0
        for i in range(MAX_CHAR):
            if occurrence[i] == 0:
                continue
            occurrence[i] -= 1
            temp_sum = factorials[size - 1 - k]
            for j in range(MAX_CHAR):
                temp_sum //= factorials[occurrence[j]]
            Sum += temp_sum
            if Sum >= n:
                res[k] = chr(i + ord('a'))
                n -= Sum - temp_sum
                k += 1
                break
            if Sum < n:
                occurrence[i] += 1
    i = MAX_CHAR - 1
    while k < size and i >= 0:
        if occurrence[i]:
            res[k] = chr(i + ord('a'))
            occurrence[i] -= 1
            i += 1
            k += 1
        i -= 1
    return ''.join(res[:k])

n = 3
string = "pqr"
print(get_nth_permute(string, n))

Input

"pqr", 3

Output

qpr