我正在解決一個遞回問題，在那里我得到一個整數陣列并要求回傳它的冪集。
例如 [1,2,3] 的冪集是 [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2, 3]]]
這是執行此操作的遞回代碼：
def powerset(array, idx = None):
if idx is None:
idx = len(array) - 1
if idx <0:
return [[]]
ele = array[idx]
subset = powerset(array,idx-1)
for i in range(len(subset)):
currentSubset = subset[i]
subset.append(currentSubset [ele])
return subset
雖然我確實了解大部分情況，但我的問題是：
當我們到達基本情況 idx<0 時，這意味著 idx 指標指向陣列之外，我們不想呼叫 array[idx]，但我的問題是 - 我們是否回傳空集“[[] ]" 只是作為填充符，以便接下來執行遞回堆疊上的頂部遞回呼叫？不然這有什么作用？
這可能是一個很高的順序，但是有人可以解釋一下示例 [1,2,3] 遞回呼叫是如何運行的嗎？這是我的理解；
我們從指向 3 的指標 idx 開始，所以 ele=3，然后我們初始化一個叫做子集的子集，它保存了 [1,2] 的冪集
這就是我感到困惑的地方，并且正在努力查看代碼如何運行……我們現在是否轉到下一批代碼，即 for 回圈？或者我們計算 [1,2] 的冪集？
遵循 Chepner 的建議：
def powerset(array):
return _powerset(array,len(array)-1)
def _powerset(array,index):
if index <0:
return [[]]
ele = array[index]
subset = _powerset(array,index-1)
for i in range(len(subset)):
subset.append(subset[i] [ele])
return subset
uj5u.com熱心網友回復：
添加print到遞回呼叫的開始和結束是一種可視化其作業方式的有用方法。
def powerset(array, idx=None, indent=0):
trace = f"{' '*indent}powerset({array}, {idx})"
print(f"{trace}...")
if idx is None:
idx = len(array)-1
if idx < 0:
print(f"{trace} -> [[]]")
return [[]]
ele = array[idx]
subset = powerset(array, idx-1, indent 1)
for i in range(len(subset)):
subset.append(subset[i] [ele])
print(f"{trace} -> {subset}")
return subset
印刷：
powerset([1, 2, 3], None)...
powerset([1, 2, 3], 1)...
powerset([1, 2, 3], 0)...
powerset([1, 2, 3], -1)...
powerset([1, 2, 3], -1) -> [[]]
powerset([1, 2, 3], 0) -> [[], [1]]
powerset([1, 2, 3], 1) -> [[], [1], [2], [1, 2]]
powerset([1, 2, 3], None) -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
請注意，0和None需要以不同的方式處理，這就是為什么您需要使用idx is None而不是not idx!
（編輯）根據注釋中的注釋，避免idx = None混淆的一種方法（而不是將其包裝在另一個函式層中）是稍微修改遞回，以便它idx首先不需要變數。與其傳遞完整陣列和指示要迭代的部分的變數，不如傳遞要為其計算冪集的陣列子集。這使得每個遞回呼叫（包括第一個）根據完全相同的“契約”進行操作——計算這個串列的冪集。
def powerset(array, indent=0):
trace = f"{' '*indent}powerset({array})"
print(f"{trace}...")
if array:
p = powerset(array[:-1], indent 1)
p.extend([s [array[-1]] for s in p])
else:
p = [[]]
print(f"{trace} -> {p}")
return p
powerset([1, 2, 3])...
powerset([1, 2])...
powerset([1])...
powerset([])...
powerset([]) -> [[]]
powerset([1]) -> [[], [1]]
powerset([1, 2]) -> [[], [1], [2], [1, 2]]
powerset([1, 2, 3]) -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
請注意，遞回呼叫的序列在每一步計算完全相同的結果，但輸入更簡單——而不是看著idx從None到1到0到-1并且不得不推理這意味著什么，我們看到arr穩步縮小到基本情況，然后堆疊的每一層都將 的最后一個元素添加arr到前一個呼叫的每個子集中。
uj5u.com熱心網友回復：
如所寫，array[:idx 1]如果傳遞了顯式索引，該函式將回傳冪集。
測驗idx < 0真的是測驗idx == -1，因為其他負值永遠不會發生。在這種情況下，函式應該計算空集的冪集，這是一個包含一個元素的集合：空集。包含空集的集由 表示[[]]。
我的印象是您試圖將遞回函式視為以令人困惑的方式撰寫的回圈。相反，您應該把它看作是一個計算某些東西的函式——在這種情況下，是一個冪集——并且碰巧將自己用作庫函式（以一種總是終止的方式）。
給定一個包含元素 x 的非空集合 S，以及一種計算較小集合 S\{x} 的冪集的方法，您如何獲得 S 的冪集？答案：對于 S\{x} 的冪集合中的每個集合，回傳兩個集合：那個集合，以及添加了 x 的那個集合。這就是這段代碼的作用。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/326812.html