递归-与in数组组合，Java中无重复 [英] Recursion - Combination with in array with no repetition in Java

问题描述

因此，我知道如何获取组合的大小-在我想要的情况下，将数组大小（在我的情况下）乘以所需数组子集的大小。我遇到的问题是获得组合。到目前为止，我已经阅读了关于stackoverflow的大多数问题，但没有提出任何建议。我认为我发现的问题是我想将创建的组合子集中的元素加在一起。所有这些都应该递归完成

So I know how to get the size of a combination - factorial of the size of the array (in my case) over the size of the subset of that array wanted. The issue I'm having is getting the combinations. I've read through most of the questions so far here on stackoverflow and have come up with nothing. I think the issue I'm finding is that I want to add together the elements in the combitorial subsets created. All together this should be done recursively

因此要澄清一下：

int[] array = {1,2,3,4,5};

子集的大小为2，组合为

the subset would be the size of say 2 and combinations would be

{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}

从这个数据我想看看子集说...等于6，那么答案将是：
{1,5} 和 {2,4} 给我一个 {1,5,2,4}

from this data I want to see if the subset say... equals 6, then the answers would be: {1,5} and {2,4} leaving me with an array of {1,5,2,4}

到目前为止，我有以下内容：

so far I have this:

 public static int[] subset(int[] array, int n, int sum){
     // n = size of subsets
     // sum = what the sum of the ints in the subsets should be 

    int count = 0; // used to count values in array later
    int[] temp = new temp[array.length]; // will be array returned

    if(array.length < n){
        return false;
    }

    for (int i = 1; i < array.length; i++) {
        for (int j = 0; j < n; j++) {
            int[] subset = new int[n];
            System.arraycopy(array, 1, temp, 0, array.length - 1); // should be array moved forward to get new combinations

                           **// unable to figure how how to compute subsets of the size using recursion so far have something along these lines**
                            subset[i] = array[i];
                            subset[i+1] = array[i+1];

                            for (int k = 0; k < n; k++ ) {
                               count += subset[k];
                            }
                           **end of what I had **

            if (j == n && count == sum) {
                temp[i] = array[i];
                                    temp[i+1] = array[i+1];
            }
        }
    } subset(temp, n, goal);

    return temp;
}

我应该如何计算可用子集的可能组合？

How should I go about computing the possible combinations of subsets available?

推荐答案

我希望你会爱上我。唯一要做的就是将结果合并到一个数组中，但是它会检查所有可能性（尝试运行程序并查看输出）:)：

I hope you will love me. Only thing you have to do is to merge results in one array, but it checks all possibilities (try to run the program and look at output) :) :

public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    int n = 2;
    subset(array, n, 6, 0, new int[n], 0);
}

public static int[] subset(int[] array, int n, int sum, int count, int[] subarray, int pos) {
    subarray[count] = array[pos];
    count++;

    //If I have enough numbers in my subarray, I can check, if it is equal to my sum
    if (count == n) {
        //If it is equal, I found subarray I was looking for
        if (addArrayInt(subarray) == sum) {
            return subarray;
        } else {
            return null;
        }
    }

    for (int i = pos + 1; i < array.length; i++) {
        int[] res = subset(array, n, sum, count, subarray.clone(), i);
        if (res != null) {
            //Good result returned, so I print it, here you should merge it
            System.out.println(Arrays.toString(res));
        }
    }

    if ((count == 1) && (pos < array.length - 1)) {
        subset(array, n, sum, 0, new int[n], pos + 1);
    }

    //Here you should return your merged result, if you find any or null, if you do not
    return null;
}

public static int addArrayInt(int[] array) {
    int res = 0;
    for (int i = 0; i < array.length; i++) {
        res += array[i];
    }
    return res;
}

这篇关于递归-与in数组组合，Java中无重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！