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;

}

Answer 1

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

Answer 2

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:

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