5

n個の配列でデカルト積を実行することに興味があります。事前に配列の数がわかれば、コードを書くことができます。たとえば、2つの配列があるとします。

int[] a = new int[]{1,2,3};
int[] b = new int[]{1,2,3};

for(int i=0; i<=a.length; i++){
    for(int j=0; j<=b.length; j++){
        System.out.println(a[i]*b[j]);
    }
}

問題は、実行時にアレイの数がわからないことです。アレイが2つある場合もあれば、100個ある場合もあります。これを行う方法はありますか？ありがとう！

4

2 に答える 2

13

この問題に取り組む1つの方法は、次のことに注意して、一度に1つずつアレイの数を継続的に減らすことです。

A0 ×A1 × A2 =（A0 ×A1 ） × A 2

したがって、次のような関数を作成できます。この関数は、2つの配列のデカルト積を計算します。

int[] cartesianProduct(int[] one, int[] two) {
    int[] result = new int[one.length * two.length];
    int index = 0;

    for (int v1: one) {
        for (int v2: two) {
            result[index] = v1 * v2;
            index++;
        }
    }

    return result;
}

これで、この関数を使用して、配列のペアを組み合わせて、デカルト積全体を含む1つの配列にすることができます。擬似コードの場合：

While there is more than one array left:
    Remove two arrays.
    Compute their Cartesian product.
    Add that array back into the list.
Output the last array.

そして、実際のJavaとして：

Queue<int[]> worklist;
/* fill the worklist with your arrays; error if there are no arrays. */

while (worklist.size() > 1) {
    int[] first = worklist.remove();
    int[] second = worklist.remove();
    worklist.add(cartesianProduct(first, second));
}

/* Obtain the result. */
int[] result = worklist.remove();

このアプローチの問題は、生成する要素の総数に比例したメモリを使用することです。これは本当に膨大な数になる可能性があります！すべての値を保存せずに一度に1つずつ出力したい場合は、より効率的な方法があります。アイデアは、異なる配列内のインデックスのすべての可能な組み合わせをリストアップし始めてから、それらの位置の値を乗算することです。これを行う1つの方法は、次に調べるインデックスが何であるかを示す「インデックス配列」を維持することです。数値をインクリメントするのと同じ方法で配列を「インクリメント」することにより、あるインデックスから次のインデックスに移動できます。そのためのコードは次のとおりです。

int[] indexArray = new int[arrays.length];
mainLoop: while (true) {
    /* Compute this entry. */
    int result = 1;
    for (int i = 0; i < arrays.length; i++) {
        result *= arrays[i][indexArray[i]]
    }
    System.out.println(result);

    /* Increment the index array. */
    int index = 0;
    while (true) {
        /* See if we can bump this array index to the next value.  If so, great!
         * We're done.
         */
        indexArray[index]++;
        if (indexArray[index] < arrays[i].length) break;

        /* Otherwise, overflow has occurred.  If this is the very last array, we're
         * done.
         */
        indexArray[index] = 0;
        index ++;

        if (index == indexArray.length) break mainLoop;
    }
}

これはO（L）メモリのみを使用します。ここで、Lは配列の数ですが、指数関数的に多くの値を生成する可能性があります。

お役に立てれば！

于 2012-05-31T20:05:07.613 に答える
1

反復の代わりに再帰を使用できますが、注意してください。StackOverflowExceptionが発生する可能性があります。

于 2012-05-31T20:03:44.267 に答える