如何正确返回ArrayList< Object>没有重复值的递归方法？ [英] How can I properly return ArrayList<Object> from recursive method without repeated values?

问题描述

我需要一个递归解决方案，该解决方案返回k个集合中n个子集的任何组合（在数学意义上）。我有一个ArrayList，我想从递归方法中返回所有可能的n尺寸子集。顺序无关紧要。
因此，如果我有一组员工{Jim，Tom，Ann，John}并且想要其中2个，我应该得到：

I need a recursive solution which returns any combination of n subset from k set (in mathematical sense). I have an ArrayList and I want return any possible n-size subsets from recursive method. Order doesn't matter. So if I have set of employees {Jim, Tom, Ann, John} and want 2 of them I should get:

{Jim Tom} {Jim Ann} {Jim John} {Tom Ann} {Tom John} {Ann John}

{Jim Tom}{Jim Ann}{Jim John}{Tom Ann}{Tom John}{Ann John}

我发现此 https://stackoverflow.com/a/16256122/10929764
，但它只会打印出结果。我对其进行了一些修改，以将任何组合添加到ArrayList并返回它，但是它无法正常工作。
这是一个代码：

I found this https://stackoverflow.com/a/16256122/10929764 but it only prints out result. I modified it a bit to add any combination to ArrayList and return it, but it doesn't work properly. Here is a code:

    public ArrayList<Employee[]> combinationsOfEmployee(ArrayList<Employee>sourceList, int selected, int startIndex, Employee[] result, ArrayList<Employee[]>allResults){
        if(selected == 0){
            for(int i=0; i<result.length; i++){
                System.out.print(result[i].getLastName() + "  ");
            }
            System.out.println("");
            allResults.add(result);
            return allResults;
        }
        for(int i=startIndex; i<=sourceList.size() - selected; i++){
            result[result.length - selected] = sourceList.get(i);
            combinationsOfEmployee(sourceList, selected - 1, i + 1, result, allResults);
        }
        return allResults;
    }

它会正确打印所有组合，但始终将相同的值添加到数组列表。所以allResults就是

It prints out properly all combinations, but adds the same values all the time to ArrayList. So allResults is

{Ann，John} {Ann，John} {Ann，John} {Ann，John} {Ann，John} {Ann，John}

{Ann, John}{Ann, John}{Ann, John}{Ann, John}{Ann, John}{Ann, John}

而不是：

{Jim Tom} {Jim Ann} {Jim John} {Tom Ann} {Tom John} {Ann John}

{Jim Tom}{Jim Ann}{Jim John}{Tom Ann}{Tom John}{Ann John}

推荐答案

您想知道为什么它可以很好地打印，而返回的列表似乎在每个位置都有完全相同的数组。

这是因为它是完全相同的数组（相同的引用到同一对象）。由于在您的解决方案中仅使用一个数组，因此在调用 allResults.add（result）时，会将引用添加到列表中的唯一数组。然后，当您寻找其他组合时，请继续对其进行修改。这就是为什么列表仅包含找到的最后一个组合的原因。

You are wondering why it prints it fine while the returned list seems to have the exact same array at each position.
That's because it's the exact same array (same reference to the same object). Since in your solution you are using only one array, when you call allResults.add(result), you add the reference to your only array in the list. Then you keep modifying it when you look for the other combinations. That's why your list only contains the last combination found.

解决方案是，每次找到组合时，通过添加当前数组的副本来添加一个新数组到您的清单。只需替换

The solution to this is to add a new array each time you find a combination by adding a copy of your current array to your list. Simply replace

allResults.add(result);

通过

allResults.add(Arrays.copyOf(result, result.length));

这样，列表中的每个元素都指向一个不同的数组。

That way, every element of your list points to a different array.

这篇关于如何正确返回ArrayList< Object>没有重复值的递归方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！