枚舉所有可能性與數組遞減值

我想寫一個遞歸方法來枚舉任意長度的數組的所有可能的值，其元素可以全部下降到一個。更正式地說，給定一個數組A，元素A_1，A_2，...，A_N和數組B與B_1，B_2 ... B_N。 A_i和B_i之間有一個關係，其中i介於1和N之間，任何元素A_i介於1和B_i之間。對於這樣的一組數組，我想爲A_i找到所有可能的狀態。枚舉所有可能性與數組遞減值

例如，陣列[1 2 3]具有以下六個可能的狀態：

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

[1 2]將產生[1 1]和[1 2]等

我試着在Python的解決方案，例如：

b = [1, 3, 3] 
n = len(b) 

a = [] 
k = 0 
r = 0 

print b 
print '------' 

def f(i, k, a, r): 
    k += 1 
    if i == n-1: 
    return False 
    for j in range(1, b[i+1]+1): 
    r += 1 
    print "i: %d b[i]: %d k: %d new: %d r: %d" % (i, b[i], k, j, r) 
    f(i+1, k, a, r) 

f(0, k, a, r)

，但我似乎無法得到正確的價值觀，我無法獲取數據結構來填充。例如[3 3]只生產有三個節點或結果的樹：

[3, 3] 
------ 
i: 0 b[i]: 3 k: 1 new: 1 r: 1 
i: 0 b[i]: 3 k: 1 new: 2 r: 2 
i: 0 b[i]: 3 k: 1 new: 3 r: 3

因爲我這樣做是想通過的問題，我很好奇如何：

蟒蛇itertools可能作出這樣的談論這個家庭的問題
這可能
任何鏈接如何更有效地去想我的做法

任何想法讚賞。

來源

2016-06-28 bonhoffer

基本上對於每一列你都有一組「允許」值。通過從這些集合中選取一個值並將其放入相關列中，可以生成一個有效的「相關」數組。你只需要嘗試所有的可能性。

遞歸地，您需要減小問題。您可以遞歸就在這裏數組的長度：

def enumerate(v):                
    if len(v) == 0:                
     yield v                 
    else:                  
     for i in range(1, v[0] + 1):            
      for rest in enumerate(v[1:]):          
       yield [i] + rest

而且你可以有itertools同樣的效果，沒有明確的復發：

def enumerate2(v):                
    from itertools import product            
    return product(*(range(1, e+1) for e in v))

來源

2016-06-28 21:57:16

哇 - 好的 - 謝謝 – bonhoffer

您正在尋找的功能/工具被稱爲「笛卡爾積」，該功能已在許多地方實現，包括itertools。

itertools.product（* iterables [重複]）

這也可能是有用的：link

實現自己的最終目標，你需要的是所謂的「辭書」排序。我不確定是否有易於使用的工具可用，因爲我不確定它是否已解決問題（取決於許多任意的排序規則）。但是，您可以查看Python文檔以開始使用，因爲他們有關於詞典輸出的一些hints。

來源

2016-06-28 21:24:13 sirgogo

感謝。我會研究一下。 – bonhoffer

我不確定下降的元素是如何笛卡兒的產品。你能解釋一下嗎？ – bonhoffer

嗯，我認爲首先你會使用笛卡爾產品來快速生成所有的可能性。然後，根據您的喜好，您將開始整理列。根據您如何調用笛卡爾產品，列表可能已被排序。 – sirgogo

枚舉所有可能性與數組遞減值

回答

相關問題