สร้าง Permutation ทั้งหมดของสตริงในลำดับ Lexicographic (พจนานุกรม) โดยใช้อัลกอริทึม Next Permutation แบบเรียกซ้ำ
ตัวอย่างโค้ด
def next_permutation(seq):
# หา index i ที่ seq[i] < seq[i+1] จากขวา
i = len(seq) - 2
while i >= 0 and seq[i] >= seq[i + 1]:
i -= 1
if i == -1:
return None
# หา index j ที่ seq[j] > seq[i] จากขวา
j = len(seq) - 1
while seq[j] <= seq[i]:
j -= 1
# สลับและกลับลำดับส่วนท้าย
seq[i], seq[j] = seq[j], seq[i]
seq[i+1:] = reversed(seq[i+1:])
return seq
def all_permutations(s):
seq = sorted(list(s))
print(''.join(seq))
while True:
seq = next_permutation(seq)
if seq is None:
break
print(''.join(seq))
all_permutations("hey")ผลลัพธ์
ehy eyh hye hey yeh yhe
คำอธิบาย
เริ่มจากลำดับที่เรียงแล้ว (lexicographically smallest)
next_permutationหา permutation ถัดไป:1. หา pivot i ที่ seq[i] < seq[i+1]
2. หา successor j > i ที่ seq[j] > seq[i]
3. สลับ i, j แล้ว reverse ส่วนท้าย
ทำซ้ำจนไม่มี next permutation (คืน None)
