Assignment 2 :  The Generation of Permutation Sequences

Submission deadline: 11:59pm, Saturday, 10 October 2015

Q1: Can I use STL?
A1: You do not need STL in this assignment. However, if you use STL, no marks will be deducted.

Q2: Can I generate all the sequences first, store them in a vector or set, and print out the unique ones?
A2: This is too slow or naive to earn full credit. We expect you to detect duplication more efficiently than that. For example, if the input is 10 'a', we expect your output is lightning faster than 10 distinct characters.

Q3: Can I use iteration instead of recursion in this assignment?
A3: Certainly. Please explain your approach with possibly educational website links in your README.

Q4: The order of my permutation result is different from the sample test case. Is it acceptable? A4: Yes. You do not need to output results in the same order. We will only check the size and content of your result.

Permutation (review) 

Often we wish to examine all the permutations of n distinct elements to determine the best one. For example, given a set of elements: a, b and c. The permutations of this set of elements are: abc, acb, bac, bca, cba and cab (All possible combinations of the given elements).  As you know, there are n! permutations for n distinct elements. 

It is painful to implement a non-recursive program to output all the permutations. With a recursive approach, you can iteratively swap the elements and print out the permutations.  The idea is simple: if the set of data contains n elements, the first step is to choose one element of the list and put it in front of the sequence.  Then permute the remaining (n-1) elements (Thisis the recursive part with one less element). When the permutation of these (n-1) elements is completed, choose another element to put in the front of the sequence, and repeat the permutation of the new set of (n-1) elements.  Obviously, the terminal case is that only one element remains in the list. 

Recursive function

Just to remind you the structure of a recursive function.

<return type>   recursive_function(  <list of parameters> ){

                    // Terminal case

                    ---------  code  -------------

                    return <return type>                   

                    // else, call this function again or do calculation

                    ---------  code  -------------

                    recursive_function ( <parameters> );

                    ---------- code --------------

                    return <return type>

}

Assignment program

In this assignment, you have to implement the permutation algorithm with the recursive function approach.  The maximum number of element size is MAX_ELEMENTS, which defaults to 10. The program first asks for the input size before generating/printing out  the permutation sequences. The input element is char data type. It means you can define a char array of size MAX_ELEMENTS at the beginning.  Then, the user input a list of elements, and all the permutations will be printed out.

If the input list contains duplicate elements, you must skip that duplicate permutations. For example, input list :  a, b, a

The output permutations should be:

aba

aab

baa

If the input list : b, a, c, a

The output permutations should be:
baca
baac
bcaa
abca
abac
acba
acab
aacb
aabc
caba
caab
cbaa
 

Sample Output:

Red color is user input

Please input array size (1-10): 4

Please input array elements: a b c a

The permutation are:
abca
abac
acba
acab
aacb
aabc
baca
baac
bcaa
cbaa
caba
caab

Continue to use this program? (C / c to continue):

In order to help you to gain maximum partial credit, you may want to first implement a permutation function for n distinct elements first.  This part would worth 30% of your grades.  Then implement the part with duplicate elements, which worths the remaining 30%.  If you believe that you have successfully implemented the full program, simply turn in the full one instead of the partial one.