Вопрос по math, multiplication, algorithm, java – Perfoming декартово произведение на массивах

4

Я заинтересован в выполнении декартового произведения для 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 массивов. Есть ли способ, которым я могу это сделать? Спасибо!

Мне непонятно: вы спрашиваете, как записать декартово произведение для каждой возможной пары массивов?b, aс .... аz, bс, бd,...bи т.д.? duffymo
docs.guava-libraries.googlecode.com/git/javadoc/com/google/… прямое произведение () goat
Этоouter product, Декартово произведение будет просто формировать кортежи элементов, а не умножать их. starblue

Ваш Ответ

2   ответа
1

Вы можете использовать рекурсию вместо итерации - но будьте осторожны - может возникнуть StackOverflowException.

Я скептически отношусь к тому, что вы попадете в исключение StackOverflowException, если у вас нет набора наборов размера 1. Даже с наборами размера 2 вы используете экспоненциальную память и только линейное пространство стека, поэтому у вас гораздо быстрее кончится память, чем у стека.
Я знаю, о каком решении вы говорите, но, если вы уже не знаете, что имеете в виду, я не думаю, что этот ответ очень поможет.
12

Одним из способов решения этой проблемы является постоянное уменьшение количества массивов по одному, отмечая, что

A0 × A1 × A2 = (A0 × A1) × A2

Следовательно, вы могли бы написать такую функцию, которая вычисляет декартово произведение двух массивов:

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

Теперь вы можете использовать эту функцию, чтобы объединять пары массивов в один массив, содержащий общее декартово произведение. В псевдокоде:

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

Проблема этого подхода заключается в том, что он использует память, пропорциональную общему количеству создаваемых вами элементов. Это может быть действительно огромное количество! Если вы просто хотите распечатать все значения по одному, не сохраняя их, есть более эффективный подход. Идея состоит в том, что вы можете начать перечислять все возможные комбинации индексов в разных массивах, а затем просто умножить значения в этих позициях. Один из способов сделать это - сохранить «индексный массив». говоря, что следующий индекс, чтобы посмотреть. Вы можете переходить от одного индекса к следующему, увеличивая & quot; массив так же, как вы увеличиваете число. Вот некоторый код для этого:

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 - количество имеющихся у вас массивов, но потенциально выдает много экспоненциальных значений.

Надеюсь это поможет!

Похожие вопросы