Chương trình tìm số phép toán tối thiểu để sắp xếp chuỗi trong Python

Cho chuỗi s. Thực hiện lặp lại phép toán sau cho đến khi chuỗi được sắp xếp: (1) Chọn i lớn nhất sao cho 1 ≤ i < len(s) và s[i] < s[i-1]. (2) Chọn j lớn nhất sao cho i ≤ j < len(s) và s[k] < s[i-1] ∀ k ∈ [i,j]. (3) Hoán đổi s[i-1] và s[j]. (4) Đảo ngược hậu tố từ i. Tìm số phép toán cần thiết (mod 10⁹+7).

Ví dụ: s = "ppqpp" → output = 2.

Giải thuật (Permutation index / Factorial number system)

Số phép toán chính là thứ tự từ điển (lexicographic rank) của hoán vị s trong tập các hoán vị của multiset ký tự, trừ 1. Dùng tần suất ký tự và giai thừa modulo.

Code Python

def solve(s):
    d = [0] * 26
    a = 0
    t = 1
    m = 10**9 + 7
    n = ord('a')
    for i, c in enumerate(s[::-1], 1):
        j = ord(c) - n
        d[j] += 1
        a = (a + sum(d[:j]) * t // d[j]) % m
        t = t * i // d[j]
    return a

s = "ppqpp"
print(solve(s))  # 2

Đầu vào / Đầu ra

Input: "ppqpp"
Output: 2