Lab2: Generating permutations in lexicographic order

CPE 202 
Lab2: Generating permutations in lexicographic order.
Goal: Write a Python program to generate all the permutations of the characters in a string. This will give you a
chance to review some simple Python constructs, i.e.. Strings and Lists and solidify your understanding of
recursion.
Your program must meet the following specification. You are to write a Python function perm_gen_lex that:
• Takes a string as a single input argument. You may assume the string consists of distinct lower case
letters (in alphabetical order). You may assume the input is a string of letters in alphabetical order.
• Returns is a list of strings where each string represents a permutation of the input string. The list of
permutations must be in lexicographic order. (This is basically the ordering that dictionaries use. Order
by the first letter (alphabetically), if tie then use the second letter, etc.
• You need to use design recipe for this lab assignment. I will offer you the step 4, which is template and
you need to cover all other steps.
Argument: abc
Returns: [abc, acb, bac, bca, cab, cba]
Step 4: Templet (Pseudo code for a recursive algorithm to generate permutations in lexicographic order.) You
must follow this pseudo code.
• If the string contains a single character return a list containing that string
• Loop through all character positions of the string containing the characters to be
permuted, for each character:
o Form a simpler string by removing the character
o Generate all permutations of the simpler string recursively
o Add the removed character to the front of each permutation of the simpler
word, and
o add the resulting permutation to a list
• Return all these newly constructed permutations
Submit you Python function in a file called perm_lex.py to Polylearn and your test program in
perm_lex_testcases.py
Note: For a string with n characters, you program will return a list contain n! strings. Note that n! grows very
quickly. For example : 15! is roughly 1.3*1012 . Thus it is probably not a good idea to test your program with
long strings.