配列の配列を反復するアルゴリズムについて

Question

nの配列a_0, ..., a_n-1、それぞれがlの要素です。各要素が別個の配列から選択されるすべての組み合わせを反復する効率的なコードを書く方法。例えば、二つの配列であれば、[0、1]、[3]、[4]、出力には、より良いアルゴリズム次いで、O（L^n）が存在しない理想的な数学的環境で

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

Answer 1

ナイトクラッカーが正しく指摘するように、あなたはO(l^n)より良くすることはできません。あなたが問題に近づく方法の1つがあります。

そのi番目のエントリ大型アレイAが配列a_iである、すなわち

A[i] = a_i

今すぐアルファベット{0,1,...,l}の長さnのすべての言葉を反復処理してください：

最後に

-(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); 
} 

申し訳ありませんが、擬似コードの矛盾はありますが、うまくいけば、ここでロジックを識別できます。

---

なお、当該実施例に基づいて、私は、最初のエントリはように最初の配列、第二のアレイから第2のエントリから来て、そしてべきであると仮定しています。これが当てはまらない場合は、引き続き上記のアイデアを使用してエントリを並べ替えることができます。しかし、これを行うと、2つの配列が共通のエントリを持つ場合に限り、繰り返しが発生する可能性があります。

Answer 2

、あなたでなければなりませんとにかく1^nの要素の出力を生成しようとしています。

プログラミング言語やアーキテクチャーのような文脈を与えるなら、O（l^n）に最も近いアルゴリズムを考えることができます。