How to return all permutations of an ArrayList of Strings

Question

I'm trying to write a method that returns one large ArrayList<ArrayList<String>> that contains smaller ArrayLists that each have a different permutation of a starting ArrayList.

This is my method:

public static ArrayList<ArrayList<String>> permute(ArrayList<String> x) {

    ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();

    while (res.size() < fac(x.size())) {  //fac method works fine

        Collections.shuffle(x);

        if (!res.containsAll(x)) {
            res.add(x);
        }

    }

    return res;
}

My approach is to basically keep reshuffling the original ArrayList, x, and check if its already in the resultant ArrayList, if it's not, then I add it. For some reason, when I try this method, the resultant ArrayList contains the same ArrayLists, even though I have an if statement which is there specifically so that wouldn't happen.

What am I missing?

Answer 1

There are three problems with your algorithm:

1. You are re-shuffling and adding the same list again and again. Try adding a x = new ArrayList(x) somewhere in the loop.
2. As pointed out by Manos, you have to use contains, not containsAll; otherwise you are checking whether all the elements inside the newly shuffled array list are contained, which is never the case, thus you are adding the same list again.
3. Your algorithms is horribly, horribly slow. Once you've got the above two problems worked out, so that the algorithm would in priciple work, the probability to get just the last permutation will be 1/n! (for n elements), so this will take really, really long.