Python非遞歸排列

有沒有人瞭解下列用於產生數字列表的所有排列的迭代算法？Python非遞歸排列

我不明白while len(stack)循環內的邏輯。有人可以解釋它是如何工作的嗎？

# Non-Recursion 
@param nums: A list of Integers. 
@return: A list of permutations. 

def permute(self, nums): 
    if nums is None: 
     return [] 
    nums = sorted(nums) 
    permutation = [] 
    stack = [-1] 
    permutations = [] 
    while len(stack): 
     index = stack.pop() 
     index += 1 
     while index < len(nums): 
      if nums[index] not in permutation: 
       break 
      index += 1 
     else: 
      if len(permutation): 
       permutation.pop() 
      continue 

     stack.append(index) 
     stack.append(-1) 
     permutation.append(nums[index]) 
     if len(permutation) == len(nums): 
      permutations.append(list(permutation)) 
    return permutations

我只是想了解上面的代碼。

來源

2016-08-17 Jobs

你有沒有嘗試用調試器通過它？理解算法的好方法。 – FujiApple

正如在您的問題的評論部分所述，調試可能提供了一種有用的方法來了解代碼的功能。不過，讓我提供一個關於你的代碼的高級視角。

首先，雖然沒有函數permute的遞歸調用，但您提供的代碼是有效遞歸的，因爲它所做的全部操作都是保留自己的堆棧，而不是使用OS的內存管理器提供的代碼。具體來說，變量堆棧保留了「遞歸數據」，可以這麼說，這是從一次遞歸調用傳遞到另一次遞歸調用。你可以，也許應該考慮將置換函數中的outer while循環的每個迭代函數作爲遞歸調用。如果你這樣做了，你會看到outer while循環以遞歸的方式幫助以深度優先的方式遍歷每個數字的排列。

注意到這一點，很容易找出每個'遞歸調用'的作用。基本上，變量排列保持的編號的當前置換，其正在循環進行時形成。變量排列存儲所發現的個數的所有排列。如你可以觀察到，置換是當LEN（置換）等於LEN（NUMS），其可以被視爲正被使用自定義堆棧實現的遞歸關係的基礎情況下，僅更新。最後，while while循環基本上選擇將哪個元素添加到正在形成的當前置換（即，存儲在變量置換中）。

就是這樣，真的。正如所建議的那樣，您可以使用調試器計算與維護堆棧相關的行上正在進行的操作。最後請注意，我個人認爲這個實現不會是非遞歸的。恰恰相反，這個遞歸解決方案不是使用操作系統提供的抽象，而是保留自己的堆棧。爲了更好地理解適當的非遞歸解決方案，您可以觀察下面提供的尋找斐波那契數的問題的遞歸和迭代解決方案的不同。正如您所看到的，非遞歸解決方案不會保留堆棧，而不是將問題分成更小的實例（遞歸），而是從較小的解決方案構建解決方案。（動態規劃）

def recursive_fib(n): 
    if n == 0: 
     return 0 
    return recursive_fib(n-1) - recursive_fib(n-2) 

def iterative_fib(n): 
    f_0 = 0 
    f_1 = 1 
    for i in range(3, n): 
     f_2 = f_1 + f_0 
     f_0 = f_1 
     f_1 = f_2 
    return f_1

來源

2016-08-17 04:32:46 ilim

從@ilim的答案是正確的，應該是公認的答案，但我只是想補充一點，不適合作爲註釋另一點。雖然我想象你正在學習這種算法作爲一個練習，應該指出的是更好的方式來進行，這取決於列表的大小，可能是用戶itertools的permutations()功能：

print [x for x in itertools.permutations([1, 2, 3])]

測試上我的機器有11個物品（39m組合）的清單花了1.7secs與itertools.permutations(x)但使用上述自定義解決方案花了76secs。但請注意，有12個項目（479m排列），itertools解決方案爆發內存錯誤。如果您需要高效地生成這種大小的排列，您最好放棄原生代碼。

來源

2016-08-17 07:32:45 FujiApple

Python非遞歸排列

回答

相關問題