An Exercise in Permutations Using Java

I came across an interesting exercise on permutations while reading the book Data Structures & Algorithms in Java by Goodrich, Tamassia and Goldwasser and thought I would write about how I solved it iteratively.

The exercise states the following:

Write a short Java program that outputs all possible strings formed by using the characters ‘c’, ‘a’, ‘r’, ‘b’, ‘o’, and ‘n’ exactly once.

At first glance solving this problem seems a bit difficult but there is a somewhat tedious but straightforward brute force approach to solve the exercise. In order to approach the problem, it’s useful to have a rudimentary understanding of the difference between permutations and combinations.   A permutation is all possible arrangements of a collection of things, where the order is important.  When order does not matter it is a combination.

Let’s look at a simple example involving a three character alphabet of  {a,b,c} with strings of size 3 to illustrate.  How many strings of size 3 can be created if repetition is allowed with the 3 character alphabet {a,b,c}?  Some simple arithmetic shows that there can be 3 different ways to fix the first character of the string, 3 ways to fix the second character of the string and 3 ways to fix the third character of the string.   This implies through simple multiplication that there is 3x3x3 = 27 ways to form a string of length 3 with the 3 character alphabet above when repetition is allowed.  However, if no repetition is allowed, then there is 3 ways to fix the first character of the string, 2 ways to fix the second character of the string and 1 way to fix the third character, resulting in 3! = 3x2x1= 6 ways to distinct ways to to form a string of length 3 with the 3 character alphabet when repetition is not allowed (or when each character is used exactly once).

It is quite easy to generate all 27 strings using a brute force approach that employs 3 nested for loops.

The output of the above program is to print all 27 possible strings of length 3 on alphabet {a,b,c} as shown below.

When no repetition is allowed an if statement is required to filter out the repetitions.  The program below prints out the 6 permutations of strings of length 3 on an alphabet of {a,b,c} when no repetition is allowed.

The output of the above program is to print the 6 distinct permutations of length 3 on the alphabet {a,b,c} as shown below.

Now to tackle the original problem posed at the beginning of this post.  The alphabet for the problem is {c, a, r, b, o, n} which is a total of 6 characters.  This implies that strings to be printed out will be of length 6 if each character is used exactly once.  Let’s calculate the total number of strings possible if repetition is allowed.  In this case,  since there are 6 characters possible for each position this means there is 6x6x6x6x6x6 = 46656 ways to print strings of six characters with repetition using the alphabet {c, a, r, b, o, n}.  What we are interested in is the number of strings without repetition, (i.e. when used exactly once).  The calculation of this figure is 6! = 6x5x4x3x2x1 = 720.  Thus, there are 720 distinct strings when each character of the alphabet {c, a, r, b, o, n} is used exactly once.

The program for solving this is shown below, it has 6 nested for loops instead of 3 because the strings are of size 6 but the brute force idea I used before in the previous program above still applies.  With 6 nested for loops one can generate all the strings of size 6 from the alphabet {c, a, r, b, o, n}.  Then all that is left is to filter out the repetitive cases as I did above in the simpler problem with an appropriate if condition.  In this particular case the if condition becomes a lot more involved and tedious to write out but when all cases are accounted for it works as expected!

The output of the above program is shown below and as calculated above there are 720 different strings of size 6 from the alphabet {c, a, r, b, o, n} when used exactly once.  On a cursory search of the Internet I noted there is a much more elegant and different way to solve this exercise problem as well which involves using recursion.   The link points to a good explanation of how the algorithm works and is well worth studying.