获取任意数量的元素的所有组合 [英] Get all combinations for arbitrary number of elements

问题描述

我该如何在Java中制作一个方法，该方法获取输入整数 n 和一个双精度数组 x ，并返回x中值中n个元素的所有组合。

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.

其中 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）

eg

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 是我从哪里开始...

This makePatterns is where I started...

推荐答案

我知道如何使用迭代算法来解决此问题，而无需递归：

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

我的想法是：

每个数组都有一个众所周知的大小（n），因此我可以立即以最终大小创建它们。

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

对于第一步（0），我用x中的数字填充数组，而其余元素未初始化：

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.

下一步（1）填充第二列：

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

我的代码使用了 int 的数组，但是对于 double 。我认为该算法可以进行任意数量的迭代。

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

这篇关于获取任意数量的元素的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！