# Permutations with repetition (Java)

From LiteratePrograms

# [edit] 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.

# [edit] 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(intx = 0; x < n; x++){intt2 =(int)Math.pow(l, x);for(intp1 = 0; p1 < permutations;){for(intal = 0; al < l; al++){for(intp2 = 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 =newArrayList<String>();for(char[]permutation : table){result.add(newString(permutation));}returnresult;

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

<<usage>>=PermutationsWithRepetition gen =newPermutationsWithRepetition("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;publicclassPermutationsWithRepetition{privateString a;privateintn;publicPermutationsWithRepetition(String a,intn){this.a = a;this.n = n;}publicList<String> getVariations(){intl = a.length();intpermutations =(int)Math.pow(l, n);char[][]table =newchar[permutations][n]; fill read}publicstaticvoidmain(String[]args){usage}}

Download code |