Generate All Permutations of a String in Java

Given any string, how many different permutations of that character set can be made? To answer that question, this Java program uses a recursive function to generate all permutations of a string passed as a command line argument. Most permutation generators that I have come across will only output permutations of the same length as the input set, e.g., enter 3 characters and the output will show permutations containing all 3 characters. This program, however, will generate all permutations of the input set from length 1 through n, where n is the total number of characters in the string. For example, if “abc” is entered, the program generates all permutations of length 1 to 3 characters: a, b, c, ab, ac, ba, bc, ca, cb, abc, acb, bac, bca, cab, cba.

Why is this useful? It probably isn’t. I wrote the code to see how the number of permutations grew with each additional character. I feel like this is also a standard introduction to Computer Science question so perhaps this will help someone do their homework assignment. From a practical standpoint, I suppose it could be used to help your Scrabble game. If you enter all of the letter tiles from your rack, this will generate all of the possible letter permutations. The code could be modified to validate those permutations against a Scrabble dictionary though it would be awfully suspicious if someone was typing into a computer/device throughout a game.

Usage

The following illustrates the code being compiled and executed using the sample set “abc”.

java Permutation [string]

[string] represents the set of characters to generate all permutations; multiple strings may be passed when separated by a space.

Source Code

import java.util.ArrayList;


public class Permutation {
  private ArrayList<String> permutations = null;
  private String characters = null;

  public static void main(String[] args) {
    Permutation p = null;
    ArrayList arrlist = null;

    for(String s: args) {
      p = new Permutation(s);
      arrlist = p.getPermutations();

      System.out.println("Generating all permutations of string: "+p.getCharacters());
      for(int i = 0; i < arrlist.size(); i++) {
        System.out.println(arrlist.get(i));
      }
      System.out.println("");
    }
  }

  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<String>();

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