Get ArrayList of all possible permutations of an ArrayList

Question

I am trying to get all possible permutations of an ArrayList that are the same length as the input arrayList. I.e. an ArrayList of 1,2,3 would result in 123, 132, 213, 231, 321, 312, not including the shorter permutations like 1, 2, 12, 13... etc. Here is the code I have so far:

public void getAllPermutations(ArrayList<coordinate> coords) {
        ArrayList<coordinate> sub = new ArrayList<coordinate>();
        permutateSub(sub, coords);
    }

    private ArrayList<ArrayList<coordinate>> permutateSub(ArrayList<coordinate> sub,
            ArrayList<coordinate> coords) {
        int n = coords.size();
        if(n == 0) System.out.println(sub);
        else {
            if(sub.size()==n) {
            System.out.println(sub);
            for(int i = 0; i<n; i++) {
                ArrayList<coordinate> a = new ArrayList<coordinate>(sub);
                a.add(coords.get(i));
                ArrayList<coordinate> b = new ArrayList<coordinate>(coords);
                b.remove(i);
                permutateSub(a, b);
            }
        }

    }

A coordinate is a class that just has x, y, and visited to hold 2D points for a project.

Currently I am using this code to print it to the console, but I would also appreciate it if someone could shed some light into how I would store this into an ArrayList>. Thanks.

Looks like this could be a duplicate of http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string — mkobit, Sep 06 '14 at 21:10
Funny, I see the declaration of method `permutateSub` as if it's supposed to return an `ArrayList>` object, but I don't see `return` anywhere in the function's code. — barak manos, Sep 06 '14 at 21:20
Oops, my mistake. Regardless, it would still return shorter permutations. — AHalbert, Sep 06 '14 at 21:26

score 5 · Answer 1 · answered Sep 06 '14 at 21:37

5

Take a look at Guava's Collections2 permutations method.

Example (source)

public void permutations () {
    List<Integer> vals = Ints.asList(new int[] {1, 2, 3});

    Collection<List<Integer>> orderPerm = Collections2.permutations(vals);

    for (List<Integer> val : orderPerm) {
        logger.info(val);
    }
}

/* output:
 [1, 2, 3]
 [1, 3, 2]
 [3, 1, 2]
 [3, 2, 1]
 [2, 3, 1]
 [2, 1, 3]
*/

answered Sep 06 '14 at 21:37

Benny Bottema

11,111
10
71
96

1

+1: No need to reinvent the wheel. Guava will be helpful in many situations anyway. – Ingo Bürk Sep 06 '14 at 21:40
In the future, I will definitely make use of this. Thanks very much. – AHalbert Sep 06 '14 at 22:12

janos · Accepted Answer · 2014-09-06T21:49:43.237

3

Here's one way to do it:

public static void permutation(List<coordinate> nums) {
    List<List<coordinate>> accum = new ArrayList<List<coordinate>>();
    permutation(accum, Arrays.<coordinate>asList(), nums);
    System.out.println(accum);
}

private static void permutation(List<List<coordinate>> accum, List<coordinate> prefix, List<coordinate> nums) {
    int n = nums.size();
    if (n == 0) {
        accum.add(prefix);
    } else {
        for (int i = 0; i < n; ++i) {
            List<coordinate> newPrefix = new ArrayList<coordinate>();
            newPrefix.addAll(prefix);
            newPrefix.add(nums.get(i));
            List<coordinate> numsLeft = new ArrayList<coordinate>();
            numsLeft.addAll(nums);
            numsLeft.remove(i);
            permutation(accum, newPrefix, numsLeft);
        }
    }
}

edited Sep 06 '14 at 21:49

answered Sep 06 '14 at 21:21

janos

120,954
29
226
236

Just to mention it, this is using Java 8 features. – Ingo Bürk Sep 06 '14 at 21:24
Thank you for contributing! However, they are not lists of Integers, they are lists of coordinates. So there are several errors that pop up involving List. – AHalbert Sep 06 '14 at 21:25
You can just search and replace `Integer` with `coordinate` – janos Sep 06 '14 at 21:29
@IngoBürk why dont you mention what Java 8 features is using as well – eldjon Sep 06 '14 at 21:30
When I do that, I get this error: The type List is not generic; it cannot be parameterized with arguments – AHalbert Sep 06 '14 at 21:31
@eldjon My goal here was to avoid that the OP can't compile the code. It's not my answer, so really such things should not have to be explained by me, but in the answer itself. Anyway: it's using Java 8's enhanced generics inference (e.g., `List foo = new ArrayList<>();`). – Ingo Bürk Sep 06 '14 at 21:37
1

@AHalbert You are probably importing the wrong `List` interface/class. – Ingo Bürk Sep 06 '14 at 21:41
The diamond operator is a Java 7 feature. I edited out of my answer because the OP doesn't seem to be using it. If there's anything else not in Java6 please point out (or be my guest and edit it out). – janos Sep 06 '14 at 21:45
@janos Oops, you're right, it's Java 7. That's what happens when I only (get to) work with Java 6. :) – Ingo Bürk Sep 06 '14 at 21:54
@IngoBürk you are correct. Thank you very much. This is what I get for taking a few months off coding! – AHalbert Sep 06 '14 at 22:13

Get ArrayList of all possible permutations of an ArrayList

2 Answers2

Linked