PermutationIterator.java (in honor of GPLv3)

To celebrate this great day, here’s a little bit of free software, released under the terms of the GNU General Public License, version 3: a Java class I wrote to find all permutations for a given string. I may later post some more in the way of documentation, but for now, por ejemplo:

PermutationIterator p = new PermutationIterator("123");
while ( p.hasNext() ) {
	System.out.println( p.next() );
}

Produces:

123
132
213
231
312
321

Since we can compute the factorial to know how many total permutations there are for a given string length, it’s a little bit faster to avoid the call to hasNext():

for (int i=0; i < p.totalPermutations(); i++) {
	System.out.println( p.next() );
}

You can also supply an integer for “N” and get permutations for an alphabetic string:

p = new PermutationIterator(20);
//...yada yada

To get:

abcdefghijklmnopqrst
abcdefghijklmnopqrts
abcdefghijklmnopqsrt
abcdefghijklmnopqstr
abcdefghijklmnopqtrs
abcdefghijklmnopqtsr
...
2,432,902,008,176,639,993 more permutations...
...
rstqponmlkjihgfedcba

And now for the code, below the fold. Happy GPLv3 launch day!

PermutationIterator.java

/*
    PermutationIterator.java - Finds all permutations for a given string.
    Copyright (C) 2007  Scott Carpenter (scottc at movingtofreedom dot org)

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see http://www.gnu.org/licenses/.
 */

import java.util.Iterator;
import java.util.NoSuchElementException;

public class PermutationIterator implements Iterator<String>
{

    private String perm;
    private String[] permArr;   //to match array of ints
    private int[] curr;         //current perm
    private int L;              //length of perm string ("N")
    private long totalPerms;
    private long counter = 0;

    public PermutationIterator(int n) {

        StringBuffer s = new StringBuffer("");
        char c = 'a';
        for (int i=0; i < n; i++) {
            s.append(c++);
        }
        initPerm(s.toString());
    }

    public PermutationIterator(String perm) {
        initPerm(perm);
    }

    private void initPerm(String perm) {
        this.perm = perm;
        L = perm.length();

        if (L > 20) {
            throw new UnsupportedOperationException(
                "Can only find permutations for N < = 20. Factorial 20 = " +
                "2,432,902,008,176,640,000 permutations. Factorial 21 would " +
                "be too much for a long data type. Apologies if two and a " +
                "half quintillion permutations is insufficient for your " +
                "application.");
        }
        totalPerms = factorial(L);
        curr = new int[L];
        permArr = new String[L];
        for (int i=0; i < L; i++) {
            curr[i] = i;
            permArr[i] = perm.substring(i, i + 1);
        }
    }

    public long totalPermutations() {
        return totalPerms;
    }

    public boolean hasNext() {
        return counter < totalPerms;
    }    

    /*
     * Algorithm by E. W. Dijkstra, "A Discipline of Programming",
     *       Prentice-Hall, 1976, p.71
     * Another example (Public Domain) by Tim Tyler from 2000 is at:
     *       http://mandala.co.uk/permutations/
     *       http://mandala.co.uk/permutations/plugin/Permutations.java
     */
    public String next() {

        counter++;
        if (counter == 1) {
            return perm;
        } else if (counter > totalPerms) {
            throw new NoSuchElementException();
        } 

        int i = L - 1;

        while(curr[i - 1] >= curr[i]) {
            i--;
        }

        int j = L;

        while(curr[j - 1] <= curr[i - 1]) {
            j--;
        }

        swap(i - 1, j - 1);

        i++;
        j = L;

        while(i < j) {
            swap(i - 1, j - 1);
            i++;
            j--;
        }

        return translateCurrToPerm();
    }

    //abstract remove() specified by Iterator is not implemented
    public void remove() {}

    private String translateCurrToPerm() {
        StringBuffer p = new StringBuffer("");
        for (int i=0; i < L; i++) {
            p.append(permArr[curr[i]]);
        }
        return p.toString();
    }

    private void swap(int idx1, int idx2) {
        int tmp;
        tmp = curr[idx1];
        curr[idx1] = curr[idx2];
        curr[idx2] = tmp;
    }

    /*
     * can only take n <= 21 (more will overflow the long data type,
     * which doesn't cause an error in Java -- just a wrap)
     * (would use BigInteger if wanted to do more)
     */
    private long factorial(int n) {
        long f = 1;
        for (int i=2; i <= n; i++) {
            f *= i;
        }
        return f;
    }
}