Chương trình Python in hoán vị chuỗi theo thứ tự từ điển (không đệ quy)

Thuật toán next_permutation lặp (iterative) để sinh hoán vị lexicographic.

Ví dụ

from math import factorial

def lex_permutations(seq):
    n = len(seq)
    for _ in range(factorial(n)):
        print(''.join(seq))
        # Tìm next permutation
        i = n - 1
        while i > 0 and seq[i-1] > seq[i]:
            i -= 1
        seq[i:] = reversed(seq[i:])
        if i > 0:
            q = i
            while seq[i-1] > seq[q]:
                q += 1
            seq[i-1], seq[q] = seq[q], seq[i-1]

s = 'bhd'
print("Chuỗi:", s)
seq = list(s)
seq.sort()
print("Hoán vị:")
lex_permutations(seq)

Kết quả

Chuỗi: bhd
Hoán vị:
bdh
bhd
dbh
dhb
hbd
hdb

Giải thích

• Sắp xếp chuỗi ban đầu để bắt đầu từ hoán vị nhỏ nhất.
• Vòng lặp factorial(n) lần.
• Bước 1: tìm i lớn nhất sao cho seq[i-1] < seq[i] (từ phải sang).
• Bước 2: đảo ngược suffix từ i.
• Bước 3: nếu i>0, tìm q > i-1 nhỏ nhất > seq[i-1], swap.
• Thuật toán chuẩn next_permutation (C++ STL).