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;
    }
}

If you enjoyed this article, please subscribe for free!
Via the atom or rss feed, or enter your email address to get updates when new entries are posted:
(Your email will not be shared nor used for anything other than sending new posts. See the policies page for more about subscriptions and privacy.)

You can skip to the end and leave a response. Pinging is currently not allowed.

Comments

  1. Your trackbacks are not working - or our blog isn’t sending the link correctly! Another nice blog, Scott! I didn’t realize you were an object oriented programmer. Got a little available time? We need you to volunteer at J!. (PHP should be not problem for you if you are a Java head! ;) )

  2. Crud! I’m getting all this great link love from opensourcecommunity.org and I’m not providing good customer service with the trackbacks. Thanks so much — I’m going to be away from my computer until tomorrow but will work diligently on fixing this when I return!

  3. And I’ve been thoroughly defeated so far. The last trackback I received was on May 20 from OSC. Nothing substantial has changed since then.

    I have a ticket in to my host.

  4. Trackbacks finally fixed! I had to turn off Apache mod_security in .htaccess:

    http://wordpress.org/support/topic/110898

You can follow any responses to this entry through the
comments feed.

Say Your Say

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>

By submitting your comment here, you agree to license it under the same Creative Commons Attribution-ShareAlike 3.0 License as the movingtofreedom.org web site. Please see policies for more information about comments and privacy.