From LiteratePrograms

Overview

Generate all permutations with repetition of a given length for a given alphabet, implemented iteratively. The number of permutations with repetition is n^l where n is the length of the alphabet and l the length of the permutations to generate. Note that as part of the iterative approach, a l * n^l matrix is created.

Implementation

• 1. We create a table for all possible permutations, with each row being one permutation. For every column x in the table, we compute l^x. For instance, for a length of 3 we would get 1, 3, 9, 27... We then, for every position in the table, fill in that computed number of elements in every column with the char in the alphabet at the position of the current column:

<<fill>>=
for (int x = 0; x < n; x++) {
    int t2 = (int) Math.pow(l, x);
    for (int p1 = 0; p1 < permutations;) {
        for (int al = 0; al < l; al++) {
            for (int p2 = 0; p2 < t2; p2++) {
                table[p1][x] = a.charAt(al);
                p1++;
            }
        }
    }
}

• 2. We now have all permutations in the table, with each permutation being one row. No we retrieve the results from the table by adding a string to the list of permutations for every row in the table:

<<read>>=
List<String> result = new ArrayList<String>();
for (char[] permutation : table) {
    result.add(new String(permutation));
}
return result;

• Sample usage: generate all permutations with repetitions of length 3 for an alphabet consisting of a, b and c:

<<usage>>=
PermutationsWithRepetition gen = new PermutationsWithRepetition("abc", 3);
List<String> v = gen.getVariations();
for (String s : v) {
    System.out.println(s);
}

• The complete class:

<<PermutationsWithRepetition.java>>=
import java.util.List;
import java.util.ArrayList;
public class PermutationsWithRepetition {
	private String a;
	private int n;
	public PermutationsWithRepetition(String a, int n) {
		this.a = a;
		this.n = n;
	}
	public List<String> getVariations() {
		int l = a.length();
		int permutations = (int) Math.pow(l, n);
		char[][] table = new char[permutations][n];
		fill
		read
	}
	public static void main(String[] args) {
		usage
	}
}

Download code