Lab 6 :: Enumeration of Permutaions

Recursion can be used effectively to solve combinatorial enumeration problems. (It does not matter if you have not heard of the word combinatorics before, it deals with counting problems. Like, how many ways to pick k objects from n objects such that ... holds)

In the midsem exam you were given a program which can print all permutations of elements of a given array. The code for that program is in file EnumerationStub.java which is the stub file for this lab assignment. Only change in the code is that it now prints permutations of a character array rather than of an integer array.

In this lab we ask you to build further on this example code. If the given array contains repetitions then method perm prints some permutations multiple times. For example, for input array x = [a b a] perm(x,0) outputs:

    
a b a
a a b
b a a
b a a
a a b
a b a

You are asked to write permNoRep method which prints each permutation only once. For example, permNoRep(x,0) should print:

   
a b a
a a b
b a a    

Another extension is about order in which permutations occur in the output. You are asked to write permNoRepLex which prints permutations in dictionary order (and each permutation appears only once). For example, permNoRepLex(x,0) should print:

a a b
a b a
b a a 

(because a a b precedes a b a in the dictionary order).

Here is the output on a longer array, y = [a b c a]:

perm(y, 0) gives:

a b c a
a b a c
a c a b
a c b a
a a b c
a a c b
b c a a
b c a a
b a a c
b a c a
b a c a
b a a c
c a a b
c a b a
c a b a
c a a b
c b a a
c b a a
a a b c
a a c b
a b c a
a b a c
a c a b
a c b a

permNoRep(y, 0) should give:

a b c a
a b a c
a c a b
a c b a
a a b c
a a c b
b c a a
b a a c
b a c a
c a a b
c a b a
c b a a

permNoRepLex(y, 0) should give:

a a b c
a a c b
a b a c
a b c a
a c a b
a c b a
b a a c
b a c a
b c a a
c a a b
c a b a
c b a a

For this lab, you may assume that character array contains only english alphabet.

You can write the above two methods by doing some incremental conceptual change to the code of perm. The first step is to clearly understand how method perm works.