如何迭代計算笛卡爾乘積？

This question問如何計算給定數量的向量的笛卡爾乘積。由於矢量的數量預先已知且相當小，因此可以使用嵌套for循環輕鬆獲得解決方案。如何迭代計算笛卡爾乘積？

現在假設你被賦予，在您所選擇的語言，向量的向量（或清單列表，或者一套套等）：

l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ]

如果有人問我，來計算其笛卡爾積，即

[ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ]

我將繼續進行遞歸。例如，在快速&骯髒的蟒蛇，

def cartesianProduct(aListOfLists): 
    if not aListOfLists: 
     yield [] 
    else: 
     for item in aListOfLists[0]: 
      for product in cartesianProduct(aListOfLists[1:]): 
       yield [item] + product

有一種簡單的方法來計算它反覆？

（注：答案並不需要在蟒蛇，反正我知道，在Python itertools做的工作做得更好，爲this question。）

來源

2010-03-10 Federico A. Ramponi

1）創建成索引列表各列表，初始化爲0，即：

indexes = [0,0,0,0,0,0]

2）從每個列表（在這種情況下，第一）屈服適當的元件。

3）增加最後一個索引。

4）如果最後一個索引等於最後一個列表的長度，則將其重置爲零並攜帶一個。重複此操作，直到沒有攜帶。

5）返回到第2步，直到索引繞回至[0,0,0,0,0,0]

它類似於如何計數作品，除了基各數位可以是不同的。

這裏的上述算法的一個Python實現：

def cartesian_product(aListOfList): 
    indexes = [0] * len(aListOfList) 
    while True: 
     yield [l[i] for l,i in zip(aListOfList, indexes)] 
     j = len(indexes) - 1 
     while True: 
      indexes[j] += 1 
      if indexes[j] < len(aListOfList[j]): break 
      indexes[j] = 0 
      j -= 1 
      if j < 0: return

下面是使用模技巧來實現它的另一種方式：

def cartesian_product(aListOfList): 
    i = 0 
    while True: 
     result = [] 
     j = i 
     for l in aListOfList: 
      result.append(l[j % len(l)]) 
      j /= len(l) 
     if j > 0: return 
     yield result 
     i += 1

注意，這個輸出結果與您的示例中的順序稍有不同。這可以通過以相反順序遍歷列表來解決。

來源

2010-03-10 18:14:24

是的。的確很容易。謝謝。 – 2010-03-10 18:29:00

我認爲你的代碼實際上比你的算法效率稍低......; P – Larry 2010-03-10 18:36:39

是的......我有另一個與算法非常匹配的版本，但認爲它相當混亂！也許我可以發佈它... – 2010-03-10 18:37:37

所有i從0到\Pi a_i_length的迭代。

for (int i = 0; i < product; i++) { 
    // N is the number of lists 
    int now = i; 
    for (int j = 0; j < N; j++) { 
     // This is actually the index, you can get the value easily. 
     current_list[j] = now % master_list[j].length; 

     // shifts digit (integer division) 
     now /= master_list[j].length; 
    } 
}

也有一些微不足道的方法來寫這個，所以你不必再做同樣的工作。

來源

2010-03-10 18:20:35 Larry

你只需要手動管理你的堆棧。基本上，做你自己的遞歸。由於遞歸看跌期權大約一個堆棧上的每個遞歸調用數據，你只是做了相同的：

Let L[i] = elements in vector i 
k = 0; 
st[] = a pseudo-stack initialized with 0 
N = number of vectors 
while (k > -1) 
{ 
    if (k == N) // solution, print st and --k 

    if (st[k] < L[k].count) 
    { 
    ++st[k] 
    ++k 
    } 
    else 
    { 
    st[k] = 0; 
    --k; 
    } 
}

沒有測試，但這個想法會工作。希望我沒有錯過任何東西。

編輯：好吧，我已經太晚了。這與計數基本相同，只是觀察它的另一種方式。

來源

2010-03-10 18:31:12 IVlad

既然你問了一個語言不可知的解決方案，這裏是一個bash，但我們可以稱之爲迭代，遞歸，它是什麼？這只是表示法：

echo {1,2,3},{4,5},{6,7},{8,9,10},{11,12},13

也許有趣。

1,4,6,8,11,13 1,4,6,8,12,13 1,4,6,9,11,13 1,4,6,9,12,13 1,4,6,10,11,13 ...

來源

2011-03-03 06:25:33

如何迭代計算笛卡爾乘積？

回答

相關問題