Get all combinations for arbitrary number of elements

Question

How can I make a method in Java which obtains input integer n, and an array of double x, and returns all combinations of n elements out of values in x.

Where x={1,2,3} and n=2,

the expected returns/combinations are {1,1},{1,2},{1,3},{2,2},{2,1},{2,3},{3,1},{3,2},{3,3} (the order is not ignored.) The number should be (int) Math.pow(x.length, n)

e.g.

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

This makePatterns is where I started...

Answer 1

Here is a recursive way of doing that.

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

---

The same way but with 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));});
}

Answer 2

I have an idea how to solve this with an iterative algorithm, without recursion:

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

My thoughts were:

Each array has a well known size (n) so I can create them immediately with the final size.

For the first step (0), I fill the arrays with the numbers from x, leaving their remaining elements uninitialized:

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

Then I fill the remaining elements of each array step by step. But during that, the number of possible combinations increases, so I makes copies of the existing arrays and add all possible combinations to the result list.

The next step (1) fills the second column:

[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, ?]

The next step fills the third column:

[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, ?]

My code uses arrays of int, but that works as well with double. I think that algorithm will work with any number of iterations.