Комбинированный генератор в JAVA

Обновить

December 2018

Просмотры

1.4k раз

2

Я пытаюсь найти все сочетания элементов в нескольких массивах. Количество массивов случайным образом (это может быть 2, 3, 4, 5 ...). Количество элементов в каждом массиве является случайным тоже.

например, у меня есть 3 массива:

String[][] array1 = {{"A1","A2","A3"},{"B1","B2","B3"},{"C1","C2"}};

Я хотел бы, чтобы сгенерировать массив со всеми возможными комбинациями:

A1, B1, C1
A1, B1, C2
A1, B2, C1
A1, B2, C2
A1, B3, C1
A1, B3, C2
A2, B1, C1
A2, B1, C2 ...

2 ответы

1

Вы можете создать комбинации с помощью «против подобной» стратегии, то есть лечить эти массивы в качестве цифр числа, как это:

public static String[][] generateCombinations(String[]... arrays) {
    if (arrays.length == 0) {
        return new String[][]{{}};
    }
    int num = 1;
    for (int i = 0; i < arrays.length; i++) {
        num *= arrays[i].length;
    }

    String[][] result = new String[num][arrays.length];

    // array containing the indices of the Strings
    int[] combination = new int[arrays.length];

    for (int i = 0; i < num; i++) {
        String[] comb = result[i];
        // fill array
        for (int j = 0; j < arrays.length; j++) {
            comb[j] = arrays[j][combination[j]];
        }

        // generate next combination
        for (int j = arrays.length-1; j >= 0; j--) {
            int n = ++combination[j];
            if (n >= arrays[j].length) {
                // "digit" exceeded valid range -> back to 0 and continue incrementing
                combination[j] = 0;
            } else {
                // "digit" still in valid range -> stop
                break;
            }
        }
    }
    return result;
}

Метод вызывается следующим образом:

generateCombinations(
            new String[]{"A1","A2","A3"},
            new String[]{"B1","B2","B3"},
            new String[]{"C1","C2"}
       )

или как это:

generateCombinations(array1)
0

Есть два основных подхода к переменной вложенности цикла. Одним из них является явным бухучет, как описано в предыдущем ответе . Другой является рекурсивным решением. В рекурсивного решения активаций рекурсивного метода в качестве хранилища локальных переменных одни и те же данные индекса , как отслеживается в явном массиве в бухгалтерии подхода.

Базовый случай для рекурсии, чтобы вернуть результат массив длиной 0, если входной содержит ноль массивы. Если вход содержит один или более массивов, генерировать результат от элементов первого массива и результата рекурсивного вызова для остальных массивов.