迴溯演算法簡例

  迴溯演算法範例，用來生成一組數字的所有排列組合。以下是詳細解釋：

程式碼逐步解釋

1. 函式定義：

   def p(nums, path):
   

   • 定義了一個名為 p 的函式，接收兩個參數：
     • nums: 還沒選擇的數字列表。
     • path: 已經選擇並排列好的數字列表。

2. 基礎條件（遞迴終止條件）：

   if not nums:
       print(path)
       return
   

   • 如果 nums 為空（即沒有剩下的數字），表示已經完成一組排列。
   • 將 path（已選擇的數字順序）印出來，並結束遞迴。

3. 遞迴迴圈：

   for i in range(len(nums)):
       p(nums[:i] + nums[i+1:], path + [nums[i]])
   

   • 使用 for 迴圈遍歷 nums 中的每個數字：
     • 每次選擇 nums[i] 作為當前排列的其中一個數字。
     • nums[:i] + nums[i+1:] 是將選中的數字 nums[i] 從列表中移除，保留剩下的數字以便繼續排列。
     • path + [nums[i]] 是將當前選擇的數字加入到 path 中，構成一個新的排列路徑。
   • 呼叫函式 p，以新的 nums 和 path 繼續遞迴，直到 nums 為空。

範例執行：

p([1, 2, 3], [])

運行流程：

1. 開始時，nums = [1, 2, 3]，path = []。
2. 選擇 1，呼叫 p([2, 3], [1])：
   • 選擇 2，呼叫 p([3], [1, 2])：
     • 選擇 3，呼叫 p([], [1, 2, 3])：
       • nums 為空，印出 [1, 2, 3]。
   • 回溯，選擇 3，呼叫 p([2], [1, 3])：
     • 選擇 2，呼叫 p([], [1, 3, 2])：
       • nums 為空，印出 [1, 3, 2]。
3. 回溯，選擇 2，呼叫 p([1, 3], [2])：
   • 重複上述過程，得到 [2, 1, 3] 和 [2, 3, 1]。
4. 回溯，選擇 3，呼叫 p([1, 2], [3])：
   • 重複上述過程，得到 [3, 1, 2] 和 [3, 2, 1]。

最終輸出：

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

總結：

• 目標： 生成 nums 列表中所有數字的排列組合。
• 演算法特點： 遞迴逐步選擇數字，當選擇完畢時回溯，嘗試其他可能性。這是一個典型的 迴溯法。
• 優點： 能有效處理組合和排列問題，逐步生成所有可能的解。