Home

Some time ago I needed to iterate through permutations and combinations of certain elements. Quickly I found this Wikipedia description of a clever algorithm to generate all swaps that are required to iterate through all possible permutations.

So I created two Iterators: PermutationsSwapIterator and PermutationsIterator. The first one generates a sequence of Swaps that you need to conduct to walk through all permutations of your List. The second one just returns all permutations of the elements in your list.

Example of use:

:::java
public void testPermutationSwapIterator() {
    List<String> strings = new LinkedList<String>();
    strings.add("aap");
    strings.add("noot");
    strings.add("mies");
    Iterator<PermutationsSwapIterator.Swap<String>> iter =
        new PermutationsSwapIterator<String>(strings);

    System.out.println(strings);
    while (iter.hasNext()) {
        Swap<String> swap = iter.next();
        System.out.println(swap.getLeft()+" <=> "+swap.getRight());
    }
}

This will output:

 [aap, noot, mies]
 mies <=> noot
 mies <=> aap
 noot <=> aap
 mies <=> noot
 mies <=> aap

As you see, these are all the swaps that you need to do to derive all possible permutations of the list of strings.

If you are interested in these permutations themselves, you can use the PermutationIterator, like so:

:::java
public void testPermutationIterator() {
    List<String> strings = new LinkedList<String>();
    strings.add("aap");
    strings.add("noot");
    strings.add("mies");
    Iterator<List<String>> iter = 
            new PermutationsIterator<String>(strings);

    while (iter.hasNext()) {
        List<String> permutation = iter.next();
        System.out.println(permutation);
    }
}

Which will output:

 [aap, noot, mies]
 [aap, mies, noot]
 [noot, mies, aap]
 [mies, noot, aap]
 [mies, aap, noot]
 [noot, aap, mies]

Essentially this is your List with the Swaps from the PermutationsSwapIterator applied to it.

Project Admins:

• Willem van Asperen

[Willem van Asperen]

It does not happen often, but once in a while you want to generate all possible permutations of a list of Objects.

In a particular case I wanted to generate all possible permutations by swapping two direct neighbours in a list. I found Even's speedup of the Steinhaus Johnson Trotter algorithm

This project contains a Java implementation of that algorithm. It contains an Iterator that generates Swap objects. Each Swap object has a left and a right element that are neighbours of each other in the permutation generated before that. So:

If you have a list [A, B, C] it will generate Swap(C, B)
Applying this Swap to the original list will result in [A, C, B]
Then the Iterator will generate Swap(A,C)
Applying this to the previous permutations results in [C, A, B]
Then comes Swap(A,B)
Result: [C, B, A]
Then Swap(C, B) -> [B, C, A]
Then Swap(A, C) -> [B, A, C]
done.

After I implemented this Swap generating Iterator it was simple to create an Iterator that just generates all possible permutations that adheres to the rule that only neighbouring elements will be swapped.

Both Iterators have a generic type, so you can supply it with lists of any type that you would need.

Have a look at the files section. There is a jar that can be used. The jar also contains the source code.