โจทย์: กำหนดสตริง หา Permutations (การเรียงสับเปลี่ยน) ทั้งหมดที่เป็นไปได้
อัลกอริทึม: Backtracking
- สลับตัวอักษรตำแหน่งปัจจุบันกับทุกตำแหน่งที่เป็นไปได้
- Recursive ไปตำแหน่งถัดไป
- Backtrack: สลับกลับคืนค่าเดิม
ตัวอย่างโค้ด Python
def to_string(lst):
return ''.join(lst)
def permute(a, l, r):
if l == r:
print(to_string(a))
else:
for i in range(l, r + 1):
a[l], a[i] = a[i], a[l] # Swap
permute(a, l + 1, r) # Recurse
a[l], a[i] = a[i], a[l] # Backtrack
# ทดสอบ
string = "TUT"
n = len(string)
a = list(string)
print("The possible permutations are:")
permute(a, 0, n - 1)
ผลลัพธ์
The possible permutations are: TUT TTU UTT UTT TUT TTU
หมายเหตุ: สตริง "TUT" มี 'T' ซ้ำ 2 ตัว ทำให้ได้ Permutations ซ้ำ 6 แบบ (3! = 6) หากต้องการ Unique ใช้ set() หรือ itertools.permutations()
วิธีง่ายกว่า: itertools.permutations
from itertools import permutations string = "TUT" perms = [''.join(p) for p in permutations(string)] unique_perms = list(set(perms)) # ลบซ้ำ print(unique_perms) # ['TUT', 'TTU', 'UTT']
ความซับซ้อน: O(n!) - เหมาะสำหรับ n ≤ 10
