關於迭代陣列陣列的算法

有n陣列a_0, ..., a_n-1，各個l元素。如何編寫有效的代碼來迭代所有組合，其中每個元素都是從不同的數組中挑選出來的。例如，如果兩個陣列是[0，1]和[3，4]，則輸出應該是關於迭代陣列陣列的算法

[0, 3] 
[0, 4] 
[1, 3] 
[1, 4]

來源

2011-07-21 Richard

這是功課嗎？你試過什麼了？ – templatetypedef

那麼價值觀總是保持其指數位置？也就是說，在上面的例子中，以下是不可能的組合：[0,1]，[3,1]，[4,3]等。 –

@Janathan M [0,1]，不是一個可以選擇的組合，因爲元素0和1都來自數組0 ... – Richard

你不可能比O(l^n)做得更好，因爲正當的爆竹指出。以下是您可以解決問題的一種方法。

做一個大陣A，其i個條目是數組a_i，即

A[i] = a_i

現在通過長度n的所有單詞的字母{0,1,...,l}迭代：

-(array*)nextWord:(array*)word { 
    array *newWord = word; 
    for (int i=n-1; i=>0; ++i) { 
     if (word[i] < l) { 
      newWord[i] = word[i]+1; 
      for (int j=i+1; j<n; ++j) { 
       newWord[i] = 0; 
      } 
      return newWord; 
     } 
    } 
    return NULL; 
}

最後，根據單詞選擇條目

word = [0, 0, ... , 0]; 
while (word != NULL) { 
    A[0][word[0]], A[1][word[1]], ... , A[n-1][word[n-1]]; 
    word = nextWord(word); 
}

對不起，僞代碼不一致，但希望你能辨別這裏的邏輯。

順便提及，基於問題的例子中，我假設第一條目應來自所述第一陣列，所述第二陣列的第二條目，等等。如果情況並非如此，那麼您仍然可以使用上述想法，然後對條目進行排列。但是，這樣做可能會導致重複，當且僅當兩個數組有共同的條目。

來源

2011-07-21 22:22:40 PengOne

在理想數學環境也沒有更好的算法然後O（L^N），則無論如何要產生l^n個元素的輸出。

如果您給我們上下文如編程語言或體系結構，我們可以想到最接近O（l^n）的算法。

來源

2011-07-21 21:06:01 orlp

實際上它是l^n –

@Yochai Timmer：Woops，你是對的。 – orlp

puesudo代碼只，,,實際上我想過使用堆棧迭代，但仍然在努力... – Richard

關於迭代陣列陣列的算法

回答

相關問題