Получить все комбинации для произвольного количества элементов

Question

Как создать метод в Java, который получает входное целое число n и массив double x и возвращает все комбинации из n элементов из значений в x.

Где x={1,2,3} и n = 2,

ожидаемые доходы / комбинации {1,1},{1,2},{1,3},{2,2},{2,1},{2,3},{3,1},{3,2},{3,3} (порядок не игнорируется.) Число должно быть (int) Math.pow(x.length, n)

например

static List<Double[]> getAll(int n, double[] x){
 List<Double[]> combinations = new ArrayList<>();
 //number of combinations should be x.length ^ n

 // when n = 1;
 for (int i=0;i<x.length;i++)
   combinations.add({x[i]}); 

 return combinations;
}

// return patterns[i] is the i th pattern 
//which contains num-elements from the input depths,
//  patterns[i][j] is the j th double in patterns[i] 
private double[][] void makePatterns(int num, double[] depths) {
    int patternN = (int) Math.pow(depths.length, num);
    double[][] patterns = new double[patternN][num];
    System.out.println(patterns.length);
    int i = 0;
    int k = 0;
    while (i < patternN) {
        for (int j = 0; j < num; j++) {
          //  System.out.println(i+" "+j+" "+(i / (int)Math.pow(depths.length, j))%depths.length);
            patterns[i][j] = x[(i / (int)Math.pow(depths.length, j))%depths.length];
        }
        i++;

    }
  return patterns;
}

Это makePatterns, где я начал ...

Answer 1

У меня есть идея, как решить эту проблему с помощью итеративного алгоритма без рекурсии:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Main
{

    static List<int[]> getAll(int n, int[] x)
    {
        List<int[]> combinations = new ArrayList<>();

        // First step (0)
        // Create initial combinations, filled with the first number.
        for (int number = 0; number < x.length; number++)
        {
            int[] array = new int[n]; // the final size of each array is already known
            array[0] = x[number]; // fill the first number
            combinations.add(array);
        }

        // In each following step, we add one number to each combination
        for (int step = 1; step < n; step++)
        {
            // Backup the size because we do not want to process
            // the new items that are added by the following loop itself.
            int size = combinations.size();

            // Add one number to the existing combinations
            for (int combination = 0; combination < size; combination++)
            {
                // Add one number to the existing array
                int[] array = combinations.get(combination);
                array[step] = x[0];

                // For all additional numbers, create a copy of the array
                for (int number = 1; number < x.length; number++)
                {
                    int[] copy = Arrays.copyOf(array, array.length);
                    copy[step] = x[number];
                    combinations.add(copy);
                }
            }
        }

        return combinations;
    }

    public static void main(String[] args)
    {
        int[] x = {3, 5, 7};
        int n = 3;

        // Calculate all possible combinations
        List<int[]> combinations = getAll(n, x);

        // Print the result
        for (int[] combination : combinations)
        {
            System.out.println(Arrays.toString(combination));
        }
    }
}

Мои мысли были:

Каждый массив имеет хорошо известный размер (n), поэтому я можно сразу создать их с окончательным размером.

Для первого шага (0) я заполняю массивы числами от x, оставляя их оставшиеся элементы неинициализированными:

[3, ?, ?]
[5, ?, ?]
[7, ?, ?]

Затем я заполните оставшиеся элементы каждого массива шаг за шагом. Но при этом количество возможных комбинаций увеличивается, поэтому я делаю копии существующих массивов и добавляю все возможные комбинации в список результатов.

Следующий шаг (1) заполняет второй столбец:

[3, ?, ?]   update to  [3, 3, ?]
            copy to    [3, 5, ?]
            copy to    [3, 7, ?]
[5, ?, ?]   update to  [5, 3, ?]
            copy to    [5, 5, ?]
            copy to    [5, 7, ?]
[7, ?, ?]   update to  [7, 3, ?]
            copy to    [7, 5, ?]
            copy to    [7, 7, ?]

Следующий шаг заполняет третий столбец:

[3, 3, ?]   update to  [3, 3, 3]
            copy to    [3, 3, 5]
            copy to    [3, 3, 7]
[3, 5, ?]   update to  [3, 5, 3]
            copy to    [3, 5, 5]
            copy to    [3, 5, 7]
[3, 7, ?]   update to  [3, 7, 3] ... and so on
[5, 3, ?]
[5, 5, ?]
[5, 7, ?]
[7, 3, ?]
[7, 5, ?]
[7, 7, ?]

В моем коде используются массивы int, но это работает также с double. Я думаю, что алгоритм будет работать с любым количеством итераций.

Answer 2

Вот рекурсивный способ сделать это.

private static void combine(int n, double[] x, List<List<Double>> combinations, List<Double> combination) {
    if (combination.size() == n) {
        combinations.add(combination);
    }
    else {
        for (int i = 0; i < x.length; i++) {
            List<Double> newCombination = new ArrayList<>(combination);
            newCombination.add(x[i]);
            combine(n, x, combinations, newCombination);
        }
    }
}


public static List<List<Double>> getCombinations(int n, double[] x) {
    List<List<Double>> combinations = new ArrayList<>();
    combine(n, x, combinations, new ArrayList<>());
    return combinations;
}


public static void main(String[] args) {
    getCombinations(2, new double[] {1,2,3}).forEach(System.out::println);
}

---

Точно так же, но с double[].

private static void combine(int n, double[] x, List<double[]> combinations, double[] combination) {
    if (combination.length == n) {
        combinations.add(combination);
    }
    else {
        for (int i = 0; i < x.length; i++) {
            double[] newCombination = Arrays.copyOf(combination, combination.length + 1);
            newCombination[combination.length] = x[i];
            combine(n, x, combinations, newCombination);
        }
    }
}


public static List<double[]> getCombinations(int n, double[] x) {
    List<double[]> combinations = new ArrayList<>();
    combine(n, x, combinations, new double[] {});
    return combinations;
}


public static void main(String[] args) {
    getCombinations(2, new double[] {1,2,3}).forEach(doubleArray -> {System.out.println(Arrays.toString(doubleArray));});
}