PermutationsIterator not generating all permutations?

[Markus Rydh]

In my tests the permutation iterator does not generate all permutations when 8 or more elements are used:

public static void main(String[] args) {
    for (int n=1; n<10; n++) {
        List<Integer> l = new ArrayList<Integer>(n);
        for (int i=0; i<n; i++) {
            l.add(Integer.valueOf(i+1));
        }
        Iterator<List<Integer>> iter = new PermutationsIterator<Integer>(l);
        int numPermutations = 0;
        while (iter.hasNext()) {
            iter.next();
            numPermutations++;
        }
        System.out.println("n=" + n + ", numPermutations=" + numPermutations + ", n!=" + factorial(n));
    }       
}

private static int factorial(int n) {
    return n==1 ? 1 : n*factorial(n-1);
}

The output is:

n=1, numPermutations=0, n!=1
n=2, numPermutations=2, n!=2
n=3, numPermutations=6, n!=6
n=4, numPermutations=24, n!=24
n=5, numPermutations=120, n!=120
n=6, numPermutations=720, n!=720
n=7, numPermutations=5040, n!=5040
n=8, numPermutations=36952, n!=40320
n=9, numPermutations=332568, n!=362880

[Willem van Asperen]

Correct! Thanks for picking this up!

I found this description of the Johnson-Trotter Algorithm that more clearly describes it: http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml

This line in the WikiPedia article "all elements greater than the chosen element have their directions set to positive or negative, according to whether they are concentrated at the start or the end of the permutation respectively" has thrown me. The mis-interpretation I made, resulted in any permutation beyond 7 to falsly miss out on quite a number of permutations.

The implementation has now been fixed in version 0.2.2.