Archive

Archive for December, 2008

Permutation Generator

December 19th, 2008 8:18 am by John Dalesandro No comments

I wanted to increase my score on the Word Challenge game on Facebook so I wrote the following recursive function to find all permutations of a character string. For example, if “abc” is entered, the code will generate all permutations of length 1 to 3 characters:  a, b, c, ab, ac, ba, bc, ca, cb, abc, acb, bac, bca, cab, cba. The code can be easily combined with a dictionary lookup function and a keypress simulator to automate the entry of valid words into Word Challenge.

import java.util.ArrayList;
 
 
public class Permutation {
  private ArrayList permutations = null;
  private String characters = null;
 
  public Permutation(String characters) {
    if((characters == null) || ("").equals(characters.trim())) {
      characters = "";
    }
    this.characters = characters;
  }
 
  public String getCharacters() {
    return characters;
  }
 
  public ArrayList getPermutations() {
    this.permutations = new ArrayList();
 
    for(int j = 1; j <= getCharacters().length(); j++) {
      permute("",getCharacters(),j);
    }
    return this.permutations;
  }
 
  protected void permute(String prefix,String s,int length) {
    String word = null;
 
    for(int i = 0; i < s.length(); i++) {
      word = prefix+s.charAt(i);
 
      if(word.length() == length) {
        permutations.add(word);
      } else {
        if(i == 0) {
          permute(word,s.substring(i+1,s.length()),length);
        } else if(i == (s.length()-1)) {
          permute(word,s.substring(0,s.length()-1),length);
        } else {
          permute(word,(s.substring(0,i)+s.substring(i+1,s.length())),length);
        }
      }
    }
    return;
  }
}
Categories: Computing Tags: ,