問題與Python遞歸

我已經寫在Python 2.7以下代碼找到N A組（AxAxA ... XA）的時間笛卡爾積 -問題與Python遞歸

prod=[] 
def cartesian_product(set1,set2,n): 
    if n>=1: 
     for x in set1: 
      for y in set2: 
       prod.append('%s,%s'%(x,y)) 
     #prod='[%s]' % ', '.join(map(str, prod)) 
     #print prod 
     cartesian_product(set1,prod,n-1) 
    else: 
     print prod 


n=raw_input("Number of times to roll: ") 
events=["1","2","3","4","5","6"] 
cartesian_product(events,events,1)

這正常工作當n = 1。但是從cartesian_product改變參數值（事件，事件1）到cartesian_product（事件，事件，2）不起作用。似乎有一個無限循環正在運行。我無法確定我在哪裏犯了一個錯誤。

來源

2017-05-26 Abdullah Shahriar

當它第二次運行時，您將'prod'作爲'set2'傳遞。由於'prod'在函數之外定義，所以set2和prod現在是相同的東西。所以當你在set2和'prod.append'中執行'for y'時，你會附加到'set2'，這會導致無限次的迭代。 – algrebe

提示：['itertools.product']（https://docs.python.org/3/library/itertools.html#itertools.product）可以完成這項工作（除非這是某種作業） – JBernardo

但是循環應該當n <1時停止。這意味着它應該在n = 2時精確運行2次@algrebe –

def cartesian_product(*X): 
    if len(X) == 1: #special case, only X1 
     return [ (x0,) for x0 in X[0] ] 
    else: 
     return [ (x0,)+t1 for x0 in X[0] for t1 in cartesian_product(*X[1:]) ] 

n=int(raw_input("Number of times to roll: ")) 
events=[1,2,3,4,5,6] 
prod=[] 
for arg in range(n+1): 
    prod.append(events) 
print cartesian_product(*prod)

輸出：

Number of times to roll: 1 

[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

你也可以通過串在你的事件列表中，但它會在元組打印字符串也。

來源

2017-05-26 18:48:13 Gahan

當您將遞歸調用的全局變量prod的引用傳遞給您時，您正在修改set2也引用的列表。這意味着set2在迭代時正在增長，這意味着迭代器永遠不會結束。

這裏不需要全局變量。返回改爲計算的產品。

def cartesian_product(set1, n): 
    # Return a set of n-tuples 
    rv = set() 
    if n == 0: 
     # Degenerate case: A^0 == the set containing the empty tuple 
     rv.add(()) 
    else: 
     rv = set() 
     for x in set1: 
      for y in cartesian_product(set1, n-1): 
       rv.add((x,) + y) 
    return rv

如果要持之以恆原始的參數的順序，使用rv = []和rv.append代替。

來源

2017-05-26 18:15:06 chepner

你的代碼在檢查cartesian_product（set1，n-1）時會總是給出[]值，而在遞歸中，它會返回n = 0並且函數總是返回[]。 – Gahan

總是返回[] –

好的，我對A^0應該是什麼以及如何創建一個只包含空元組的集合感到困惑。現在應該修復。 – chepner

在遞歸調用cartesian_product(set1,prod,n-1)內部，您正在傳遞列表prod，並且您又將值附加到它，所以它隨着時間的推移而增長，並且內部循環從不終止。也許你可能需要改變你的實現。

來源

2017-05-26 18:15:30

問題與Python遞歸

回答

相關問題