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

Sinh tất cả hoán vị của chuỗi theo thứ tự lexicographic dùng thuật toán next_permutation đệ quy.

Ví dụ

from math import factorial

def next_perm(seq):
    if len(seq) == 0:
        return None
    nxt = next_perm(seq[1:])
    if nxt is None:
        seq[1:] = reversed(seq[1:])
        q = 1
        while q < len(seq) and seq[0] > seq[q]:
            q += 1
        if q == len(seq):
            return None
        seq[0], seq[q] = seq[q], seq[0]
        return seq
    else:
        return [seq[0]] + nxt

def lexicographic_permutations(s):
    seq = list(s)
    for _ in range(factorial(len(seq))):
        print(''.join(seq))
        nxt = next_perm(seq)
        if nxt is None:
            seq.reverse()
        else:
            seq = nxt

text = input("Nhập chuỗi: ")
print("Hoán vị lexicographic:")
lexicographic_permutations(text)

Kết quả

Nhập chuỗi: hey
Hoán vị lexicographic:
hey
hye
yeh
yhe
ehy
eyh

Giải thích

• next_perm đệ quy tìm hoán vị tiếp theo theo thứ tự từ điển.
• Cơ chế: tìm suffix giảm dần, swap với phần tử nhỏ hơn ngay trước, đảo suffix.
• Gọi factorial(n) lần để in tất cả hoán vị.
• Khi next_perm trả về None (đã ở hoán vị cuối), đảo ngược về đầu.