递归地创建组合列表

Question

我正在尝试使用递归实现组合方法。我已经使用 for 循环完成了它，但想通过递归来处理它。

该方法获取两个输入并创建所有可能的组合。它应该将组合存储在我称之为“组合”的实例变量中。我尝试了不同的代码，但它们无法正常工作。我认为递归回溯是解决这个问题的最佳方法。

例如，object.pe1.combination(4,3) 会创建如下内容： image of combination list


    // Instance variable needed for this problem
    ArrayList<Integer[]> combination; 
    private int size;



    // To calculate all the possible combinations
    private int factorial(int x){
        if (x == 0) {
            return 1;
        }
        else {
            return x * factorial(x - 1);
        }
    }
    
    void combination(int n, int r) {
        
        // formula for calculating the combination of r items selected among n: n! / (r! * (n - r)!)
        int noc = factorial (n) / (factorial (r) * factorial (n - r)); // number of combinations 
        
        this.combination = new ArrayList<Integer[]>(noc); // 2D array. Each slot stores a combination

        if (noc == 0) {
            
        }
        else {
            this.combination = new ArrayList<Integer[]>(noc);
            int[] arr = new int[n];
            int[] temparr = new int[r];
            arr = createCombination(temparr, 0, r);
        }
    }


        private int[] createCombination(int[] temparr, int index, int r) {
        // this is where I am stuck
        temparr[0] = index;
        
        if (temparr[r] == 0) {
            temparr = new int[r - 1];
            temparr = createCombination(temparr, index + 1, r - 1);
        }
        
        else {
            return temparr;
        }
    }

Answer 1

任何算法的递归实现都由两部分组成：

base case - 终止递归调用分支的条件，代表预先知道结果的边缘情况；
递归案例 - 逻辑驻留和递归调用的部分。

对于此任务，基本情况 将是组合大小等于目标大小（在您的代码中表示为 r，在代码中下面我给它起了个名字targetSize).

递归逻辑的解释:

每个方法调用都跟踪自己的 combination；
除非达到 targetSize，否则每个组合都用作 blue-print for other combinations；
数据源中的每个项目都可以使用 only once，因此当它被添加到组合时，必须从源中删除它。

您用来存储组合的类型 ArrayList<Integer[]> 不是一个好的选择。数组和泛型不能很好地结合在一起。 List<List<Integer>> 更适合此目的。

另外在我的代码中 List 被用作数据源而不是数组，这不是一个复杂的转换并且可以很容易地实现。

注意代码中的注释

    private List<List<Integer>> createCombination(List<Integer> source, List<Integer> comb, int targetSize) {
        if (comb.size() == targetSize) { // base condition of the recursion
            List<List<Integer>> result = new ArrayList<>();
            result.add(comb);
            return result;
        }

        List<List<Integer>> result = new ArrayList<>();
        Iterator<Integer> iterator = source.iterator();
        while (iterator.hasNext()) {
            // taking an element from a source
            Integer item = iterator.next();
            iterator.remove(); // in order not to get repeated the element has to be removed

            // creating a new combination using existing as a base
            List<Integer> newComb = new ArrayList<>(comb);
            newComb.add(item); // adding the element that was removed from the source
            result.addAll(createCombination(new ArrayList<>(source), newComb, targetSize)); // adding all the combinations generated
        }
        return result;
    }

对于输入

    createCombination(new ArrayList<>(List.of(1, 2, 3)), new ArrayList<>(), 2));

它将产生输出

[[1, 2], [1, 3], [2, 3]]

递归地创建组合列表

Create a list of combinations recursively

java

math

recursion

combinatorics

recursive-backtracking