使用递归排列数字的 ArrayList [英] Permutation of an ArrayList of numbers using recursion

问题描述

我正在尝试通过创建 ArrayList 的排列来学习递归:

I am trying to learn recursion by creating a permutation of an ArrayList:

 {1,2,3}

但是递归调用的概念一直在我脑海中浮现.我知道如何进行迭代解决方案.但是有没有一种系统的方法可以将我的迭代解决方案转换为递归解决方案?

but the concept of recursive calls just keeps going over my head. I know how to do an iterative solution. but is there a systematic way to convert my iterative solution to recursive?

private static ArrayList<ArrayList<Integer>> permutate(ArrayList<Integer> list) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    result.add(new ArrayList<Integer>());

    for (int i = 0; i < list.size(); i++) {
        ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>();

        for (ArrayList<Integer> l : result) {
            for (int j = 0; j < l.size()+1; j++) {
                l.add(j, list.get(i));

                ArrayList<Integer> temp = new ArrayList<Integer>(l);
                current.add(temp);

                l.remove(j);
            }
        }

        result = new ArrayList<ArrayList<Integer>>(current);
    }

    return result;

}

推荐答案

public static List<List<Integer>> listPermutations(List<Integer> list) {

    if (list.size() == 0) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList<Integer>());
        return result;
    }

    List<List<Integer>> returnMe = new ArrayList<List<Integer>>();

    Integer firstElement = list.remove(0);

    List<List<Integer>> recursiveReturn = listPermutations(list);
    for (List<Integer> li : recursiveReturn) {

        for (int index = 0; index <= li.size(); index++) {
            List<Integer> temp = new ArrayList<Integer>(li);
            temp.add(index, firstElement);
            returnMe.add(temp);
        }

    }
    return returnMe;
}

为了测试这个，我使用了:

To test this I used:

public static void main(String[] args) throws Exception {

    List<Integer> intList = new ArrayList<Integer>();
    intList.add(1);
    intList.add(2);
    intList.add(3);
    List<List<Integer>> myLists = listPermutations(intList);

    for (List<Integer> al : myLists) {
        String appender = "";
        for (Integer i : al) {
            System.out.print(appender + i);
            appender = " ";
        }
        System.out.println();
    }

}

这给了我输出:

1 2 3
2 1 3
2 3 1
1 3 2
3 1 2
3 2 1

这篇关于使用递归排列数字的 ArrayList的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！