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
– Ben, Commented Jun 27, 2014 at 20:49
I'm returning an ArrayList of an ArrayLists of permutations. — user3718441
– user3718441, Commented Jun 27, 2014 at 20:52
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
– Tesseract, Commented Jun 27, 2014 at 21:40
That is the answer, don't do what already exists. stackoverflow.com/a/25704984/5218261 — Yegor Dovganich
– Yegor Dovganich, Commented Aug 31, 2017 at 14:05

Mike Elofson · Accepted Answer · 2014-06-27 21:03:50Z

4

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:

answered Jun 27, 2014 at 21:03

Mike Elofson

2,0371 gold badge11 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

awksp Over a year ago

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 Over a year ago

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.

Yakir Yehuda · Accepted Answer · 2014-06-27 23:31:15Z

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.

Collectives™ on Stack Overflow

Permutation of an ArrayList of numbers using recursion

2 Answers 2

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related