ใช้ Iterative Next Permutation Algorithm สร้าง Permutation ทั้งหมดแบบ Lexicographic โดยไม่ต้องการ Recursion
ตัวอย่างโค้ด
def next_permutation(arr):
i = len(arr) - 2
while i >= 0 and arr[i] >= arr[i + 1]:
i -= 1
if i == -1:
return False
j = len(arr) - 1
while arr[j] <= arr[i]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1:] = reversed(arr[i+1:])
return True
s = 'bhd'
arr = sorted(list(s))
print(''.join(arr))
while next_permutation(arr):
print(''.join(arr))ผลลัพธ์
bdh bhd dbh dhb hbd hdb
คำอธิบาย
เริ่มจาก sorted array (permutation แรก)
next_permutationแก้ไข array ในที่เดียว (in-place) คืน True ถ้ามี nextขั้นตอนเดียวกับ recursive version แต่ทำในลูป while
Memory: O(1) extra space (ไม่รวม output)
เหมาะสำหรับสตริงยาวที่ recursion depth อาจเกิน
