recursion - 如何利用Java求排列组合

问题描述

问 题

假设我有一个ArrayList<Integer> [0, 1, 2, 3, 4, 5, 6, 7, ......n], 选择 m 个元素组成另外一个ArrayList<Integer>, 然后把所有组合储存在一个ArrayList<ArrayList<Integer>> 里。 每个元素可以多次使用。

例如 n = 3, m = 2. 然后所有结果是[[0, 0],[0, 1],[0, 2],[1, 0],[1, 1],[1, 2],[2, 0],[2, 1],[2, 2]].

下面这些是我写的，然而非常难看。 如果n, m 的数值比较大的时候，我这根本写不下去。

请问有人能帮我用递归写下吗，我被这个卡了好久。

    // create a blank arrayList to store raw data
    ArrayList < Integer > originalData = new ArrayList < > ();

    // create a blank arrayList to store all combinations
    ArrayList < ArrayList < Integer >> allCombinations = new ArrayList < > ();

    // the length of the arraylist we just created.
    // suppose it's 4 now.
    int x = 4;

    // generate elements
    for (int i = 0; i < x; i++) {
        originalData.add(i);
    }

    // how many elements we need in each combination.
    // suppoer it's 3 now
    int y = 3;

    // the number of for-loop is y
    for (int i = 0; i < originalData.size(); i++) {
        for (int j = 0; j < originalData.size(); j++) {
            for (int k = 0; k < originalData.size(); k++) {

                // create a new arrayList to store all elements in a single combination
                ArrayList < Integer > singleItem = new ArrayList < > ();
                singleItem.add(originalData.get(i));
                singleItem.add(originalData.get(j));
                singleItem.add(originalData.get(k));

                // store all combinations to an arraylist
                allCombinations.add(singleItem);

            }
        }
    }
    System.out.println(allCombinations);
}

解决方案

public class Solution {

    public static List<List<Integer>> permute(int[] data, int m) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> ints = Arrays.stream(data).boxed().collect(Collectors.toList());
        dfs(result, ints, new Stack<>(), 0, m);
        return result;

    }

    public static void dfs(List<List<Integer>> result, List<Integer> data, Stack<Integer> list, int index, int m) {

        // 树的深度最大为m，终止递归
        if (index >= m) {
            // 节点为最后的结果，需要拷贝数据
            result.add(new ArrayList<>(list));
            return;
        }
        for (Integer value : data) {

            //       null
            //    /   |   \
            //   1   2    3
            // / | \
            //11  12  13
            list.add(value);
            // 递归，深度+1
            dfs(result, data, list, index + 1, m);
            // 回溯
            list.pop();
        }

    }

    public static void main(String[] args) {
        List<List<Integer>> lists = permute(new int[]{1, 2}, 3);
        lists = permute(new int[]{1, 2,3}, 2);
    }
}

这篇关于recursion - 如何利用Java求排列组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！