CISC121 Fall 2022 - Assignment 4
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CISC121 Fall 2022 - Assignment 4
Due: Wednesday November 23rd 11:59pm (EDT)
Notes:
● Your assignment should follow the python style guide, and any other style/commenting expectations as discussed in lecture
● By submitting the assignment, you agree that you have followed the Queen’s Academic Integrity policy, and that your assignment was completed independently.
Scenario
In discrete mathematics and computer science, we say that a permutation of a string is some reordering of the letters within the string. That is ‘gum’ is a permutation of ‘ mug’ . We can list all permutations on three letters ‘abc’ :
abc bac cab
acb bca cba
For any string of length n there are n! permutations. We can count this by considering the number of choices for each position as we build up the string. At first, we have n choices, any possible letter. For the next position, we can no longer choose the letter that has already been placed, so we only have n- 1 choices. We continue in such a manner until all n letters have been placed in the permutation. There are n⋅(n- 1)⋅(n-2) ⋅ ⋅ ⋅3⋅2 ⋅ 1 choices for each position, and thus n! many permutations on an n length string.
Imagine you are working on an anagram builder. You want to find all possible permutations of some given words, to see which words may be an appropriate anagram. While this task is generally quite difficult, we will focus on breaking the problem down into a few basic steps. In order to build such a solver, we will first need to take in a word from the user, and clean it to fit our usual word requirements (all upper case, no symbols or spaces – you may use this from Assignment 1). Then, we may find it useful to order the letters from a to z, this is a strategy many competitive Scrabble players use when sorting their tiles. Once we have a sorted list, we can then find all possible permutations, while ignoring any duplicate letters. We will implement this list of all possible permutations recursively.
Question 1 – 10 marks
For the first part of this assignment, you will start by acquiring a string that we will then find the permutations on. First, in your main program you will ask the user for a string of up to 10 letters (not characters). You may assume that the user has entered a valid string, but you will need to then remove all the spaces, digits, and special characters. Then, convert all the remaining letters to uppercase. You may notice that this is the same requirement as Assignment 1, and you are free to re-use this code. [Hint: while cleaning the string, be sure to only consider the first 10 LETTERS, this may require a counter.]
Once the string has been properly called, you will call your recursive implementation either Mergesort or Quicksort as defined in class [Note: you may choose either, there are no restrictions]. This implementation will sort a user entered string of up to 10 letters. The string must be cleaned prior to entering the sort. Notice, the function returns a sorted string, that is different from the original string.
a4.py
import functions
##Your main program here##
functions.py
def merge_string(my_word): # (or quick_string) 1
""" 2
------------------------------------------------------- 3
Sorts a string from a to z using the recursive merge (or quick) sorting 4
algorithm as learned in class. 5
6
Parameters: 7
my_word - a string containing at most 10 letters, all upper 8
case, with no spaces, symbols, or punctuation. 9
Returns: 10
sorted_string - a new string that is sorted 11
------------------------------------------------------- 12
""" 13
Question 2 -- 20 marks
Now that we have a sorted word, we will find all possible permutations. First, we may remove all the repeated letters. Since our string is sorted, this is a quick linear search. You are not required to remove the letters “ in-place” and may use an additional string to store the unique letters so long as the new string remains sorted.
You must write a recursive function that finds all permutations of a string of length n, where n is no larger than 10. [Note: this limit is to avoid concerns of complexity, rather than provide a restriction on your solutions.] Return to your main code, and call this function.
functions.py
def string_permutations (my_word): 1
""" 2
------------------------------------------------------- 3
Finds all permutations of a given string. Stores them in a list of 4
strings, and returns the list 5
------------------------------------------------------- 6
Parameters: 7
my_word - a SORTED string containing at most 10 letters 9
Returns: 10
Permutations_list = a list of strings of all possible permutations 11
------------------------------------------------------- 12
""" 13
Requirements
1. a4.py: This is your main program. You should be sure to import your functions. Question 1:
○ You must ask the user for a string
○ You do not need to check if it is a valid string, or for command insertions, etc. You may assume it is a valid string.
○ You must remove all non-letters, and convert all remaining letters to uppercase. You may use your code from Assignment 1.
○ You must be sure your final word has no more than 10 letters. It is advised that you check this while cleaning your word, by keeping a counter, although that is not required.
Question 2:
○ You must continue your main program, after calling the merge (or quick) sort for the string. First, you should remove all duplicate letters. Then, on your final word, you should call the recursive permutations function (which should also be in your functions file.
○ You do not need to remove the duplicates in place, and may use an additional string. This may be done with a function, but it is not required.
○ If you use any additional functions, add them to your functions file, and import them. Be sure to use proper documentation.
2. functions.py This is the file that contains your merge_string() sort.
○ You may follow the implementation from class, where we used the merge and quicksort for lists
○ You must be sure that you are sorting a string, and returning a string
○ Recursively call the permutations. Hint: you must consider how we can build the permutations of length 5 from the permutations of length 4
To Submit:
Submit the following files as a SINGLE zip file:
1. A4.py Your main program for both questions.
2. functions.py: Your functions, that you must import into your main
3. Testing.txt: Include all tests you run. This should be for all functions and the main program. Run a few tests, and describe what you did.
2023-01-12