หา permutation ที่ n ในลำดับเลขโครงภาษา (Lexicographic) ของสตริงใน Python

โจทย์: กำหนดสตริงตัวพิมพ์เล็ก หา permutation ที่ n (1-indexed) เมื่อเรียงลำดับแบบ dictionary order

ตัวอย่าง: "pqr", n=3 → permutations: [pqr, prq, qpr, qrp, rpq, rqp] → คำตอบ "qpr"

อัลกอริทึม (Factorial Number System)

1. คำนวณแฟกทอเรียลล่วงหน้า
2. นับความถี่ตัวอักษร (occurrence array)
3. สร้างผลลัพธ์ทีละตัว: ลองวางตัวอักษรแต่ละตัว คำนวณจำนวน permutation ที่เป็นไปได้ ถ้ามากกว่าหรือเท่า n → เลือกตัวนั้น ลบ n ตามที่ข้ามไป
4. เติมตัวอักษรที่เหลือเรียงจาก z ถึง a

ตัวอย่างโค้ด

MAX_CHAR = 26
MAX_FACT = 20
factorials = [1] * MAX_FACT
for i in range(1, MAX_FACT):
    factorials[i] = factorials[i-1] * i

def get_nth_permute(string, n):
    size = len(string)
    occurrence = [0] * MAX_CHAR
    for ch in string:
        occurrence[ord(ch) - ord('a')] += 1
    
    res = [''] * 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
            k += 1
        i -= 1
    return ''.join(res[:k])

print(get_nth_permute("pqr", 3))  # qpr

ผลลัพธ์

qpr

หมายเหตุ: อัลกอริทึมนี้ทำงานได้แม้สตริงมีตัวอักษรซ้ำ (multiset permutation)