Permutation of an ArrayList of numbers using recursion

Question

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;

}

why do you wrap an arraylist in another...? In any case, think about it like this, permuting a list {a, b, c, d,..} could be done by picking a random element, say b, removing it, and then permute the rest of the list. So that result = {b} union {permutation of rest of list}. There's your recursion — Ben, Jun 27 '14 at 20:49
I'm returning an ArrayList of an ArrayLists of permutations. — user3718441, Jun 27 '14 at 20:52
check this out: http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string — Ed Morales, Jun 27 '14 at 21:30
There is a systematic way of designing recursive methods. First you imagine that there already exists a working version of that method somewhere. And then you ask yourself, how can you write your method by making use of that other preexisting one but with the condition that you have to reduce the problem to a (slightly) smaller one before you make the recursive call. Once you have written that you add a stopping condition and check the resulting method again to see if any additional tweaking is needed. — Tesseract, Jun 27 '14 at 21:40
That is the answer, don't do what already exists. https://stackoverflow.com/a/25704984/5218261 — Yegor Dovganich, Aug 31 '17 at 14:05

score 4 · Accepted Answer · answered Jun 27 '14 at 21:03

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();
    }

}

Which gave me the output:

You know, as nice as it is that you're answering questions, I think that it'd be nice to at least *explain* what you're doing. You're doing OP no favors by writing code for him/her without any explanation. — awksp, Jun 27 '14 at 21:04
In addition, you're not *technically* answering the question: "is there a systematic way to convert my iterative solution to recursive?" Saying "Here's a recursive solution" doesn't strictly answer that. — awksp, Jun 27 '14 at 21:05

score -1 · Answer 2 · answered Jun 27 '14 at 23:31

Here you go mate:

main:
ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(3);
    ArrayList<ArrayList<Integer>> ans = permutate(list, null, 0);


private static ArrayList<ArrayList<Integer>> permutate(
        ArrayList<Integer> list, ArrayList<Integer> curlist, int cur) {
    if (cur == 0) {
        ArrayList<ArrayList<Integer>> totalAns = new ArrayList<ArrayList<Integer>>();
        for (Iterator<Integer> iterator = list.iterator(); iterator
                .hasNext();) {
            Integer integer = (Integer) iterator.next();
            ArrayList<Integer> tmp3 = new ArrayList<Integer>();
            tmp3.add(integer);
            ArrayList<ArrayList<Integer>> firstAns = permutate(list, tmp3,
                    cur + 1);
            for (Iterator<ArrayList<Integer>> iterator2 = firstAns
                    .iterator(); iterator2.hasNext();) {
                ArrayList<Integer> arrayList = (ArrayList<Integer>) iterator2
                        .next();
                totalAns.add(arrayList);

            }
        }
        return totalAns;
    }
    if (cur == list.size()) {
        ArrayList<ArrayList<Integer>> tmp2 = new ArrayList<ArrayList<Integer>>();
        tmp2.add(curlist);
        return tmp2;
    }

    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < list.size(); i++) {
        if (!curlist.contains(list.get(i))) {
            @SuppressWarnings("unchecked")
            ArrayList<Integer> tmp = (ArrayList<Integer>) curlist.clone();
            tmp.add(list.get(i));
            ArrayList<ArrayList<Integer>> recAns = permutate(list, tmp,
                    cur + 1);
            for (int k = 0; k < recAns.size(); k++) {
                ans.add(recAns.get(k));
            }
        }

    }
    return ans;
}

As I commented on Mike's answer above, you're *technically* not answering the question "is there a systematic way to convert my iterative solution to recursive?" Saying "Here's a recursive solution" doesn't strictly answer that. In addition, explaining the code (and your thought process) would make this more likely to actually be an answer. — awksp, Jun 28 '14 at 04:13

Permutation of an ArrayList of numbers using recursion

2 Answers2

Linked