Permutations ใน Python - สร้าง Permutation ทั้งหมด

สมมติว่าเรามีชุดจำนวนเต็มที่ไม่ซ้ำกัน เราต้องหา permutations ทั้งหมดที่เป็นไปได้ ตัวอย่าง อาร์เรย์ [2,1,3] ผลลัพธ์คือ [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

ขั้นตอนการทำงาน (Recursive Backtracking with Swapping)

1. ใช้ recursive approach ฟังก์ชันรับ list, start, curr, res
2. ถ้า start > len(list) - 1 ใส่ curr ลง res คืนค่า
3. วนลูป i จาก start ถึง len(list) - 1:
   • สลับองค์ประกอบที่ index start และ start + (i - start)
   • เรียก permutation(list, start + 1, curr + [list[start]], res)
   • สลับกลับ (backtrack)
4. เรียกเริ่มต้น permutation(arr, 0, [], res)

ตัวอย่างโค้ด (Python)

class Solution(object):
    def permute(self, nums):
        result = []
        self.permute_util(nums, 0, [], result)
        return result

    def permute_util(self, given_list, start, curr, result):
        if start > len(given_list) - 1:
            result.append(curr)
            return
        for i in range(start, len(given_list)):
            self.swap(given_list, start, start + (i - start))
            self.permute_util(given_list, start + 1, curr + [given_list[start]], result)
            self.swap(given_list, start, start + (i - start))

    def swap(self, nums, index1, index2):
        temp = nums[index1]
        nums[index1] = nums[index2]
        nums[index2] = temp

ob1 = Solution()
print(ob1.permute([1,2,3,4]))

อินพุต

[1,2,3,4]

เอาต์พุต

[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,3,2],[1,4,2,3],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,3,1],[2,4,1,3],[3,2,1,4],[3,2,4,1],[3,1,2,4],[3,1,4,2],[3,4,1,2],[3,4,2,1],[4,2,3,1],[4,2,1,3],[4,3,2,1],[4,3,1,2],[4,1,3,2],[4,1,2,3]]