Permutation of an ArrayList

Question

There's a lot of guide on finding Permutation for a String, but how would I do this for every element in an ArrayList? Given that:

ArrayList<String> list = [bob, cat, dog]

Output:

[bob, cat, dog]
[bob, dog, cat]
[dog, bob, cat]
[dog, cab, bob]
....

Here's a code that I have that will permute a single word:

public class permutations {

public ArrayList<String> performPermutations(String s){
    ArrayList<String> arrayList = new ArrayList<String>();
    if (s == null) {
        return null;
    }

    else if (s.length() == 0) {
        arrayList.add("");
        return arrayList;
    }

    else {
        for (int i = 0; i < s.length(); i++) {
            ArrayList<String> remaining = performPermutations(s.substring(0, i) + s.substring(i + 1));
            for (int j = 0; j < remaining.size(); j++) {
                arrayList.add(s.charAt(i) + remaining.get(j));
            }
        }
        return arrayList;
    }
}


public static void main(String[] args) {
    permutations p = new permutations();
    ArrayList<String> arr = p.performPermutations("abc");
        for(int i = 0; i<arr.size();i++) {
            System.out.println(arr.get(i));
        }
 }

Permuting the elements of an ArrayList of size `N` is the same as permuting the numbers `0 ... (N - 1)`, because if you can do that you can go from a permutation of numbers to a permutation of elements by just getting each element in turn. Do some research on that to see if you can find your answer that way. — Mshnik, Jan 19 '15 at 03:53

score 0 · Answer 1 · edited May 23 '17 at 11:56

0

See the code here for permutation of numbers :

Java code for permutation of a list of numbers

And now in your case, the list of numbers will be nothing but the list of indices for the ArrayList of strings. So basically permutation of indices will lead to permutation of the strings.

edited May 23 '17 at 11:56

Community

1
1

answered Jan 19 '15 at 04:13

Wajahat

1,593
3
20
47

Thanks for the answer, but I'm having problem understanding how to iterate through the ArrayList... From my example above, to recursively iterate through a String it uses: ArrayList remaining = performPermutations(s.substring(0, i) + s.substring(i + 1)); How would I do this in an ArrayList? I understand that I would need to set a boolean of *.size() in a for loop... – the1 Jan 19 '15 at 13:20
Disregard. I got it figured out! Thanks everyone! – the1 Jan 22 '15 at 22:52

score 0 · Answer 2 · answered Jan 19 '15 at 04:24

A simple solution to reverse anything (words in a sentence, items in a list etc) is to use a stack:

create a stack
loop on each item of your list, push the current item on the stack
loop on each item of the stack, pop the current item in a new list

That may not be the best in terms of performance though, but it works with everything as long as you can put it in a stack. And the two loops are not embedded in each other, so it's better than your example.

Permutation of an ArrayList

2 Answers2