Description
1 Permutations in Lexicographic Order
1.1 Specification
We are going to write a Python program to generate all the permutations of the characters in a string. This will
give you a chance to review some Python constructs (e.g. strings and lists) and also solidify your understanding of
recursion.
Your program must meet the following specifications. In a file named perm_lex.py, You are to write a Python
function perm_gen_lex that:
• Takes a string as a single input argument. You may assume that the input string will be 0 or more unique
lower-case letters in alphabetical order.
• Returns a Python list of strings where each string represents a permutation of the input string. The list of
permutations must be in lexicographic (i.e. dictionary) order.
Note: if you follow the pseudocode below, your list will be constructed such that this condition will be met.
Do not sort the list.
CPE 202 Assignment 1, Page 2 of 5
• Is well structured, commented, and easy to read. Contains a docstring explaining its purpose. Adheres to the
style in PEP 8.
• Is recursive and follows the pseudocode below.
perm_gen_lex(s)
Input: A string
Output: A list of all permutations of the characters in s in lexicographic order
for each character c in s do
Form a simpler string, t, by removing c from s
Generate all permutations of t recursively # i.e. call perm_gen_lex(t)
for each permutation p of t do
Add c to the front of p and add the result to your list of permutations
return the list of permutations
Note, my simple pseudocode never mentions a base case. Your code will need one to function correctly. Think
about what it should be and what you should return in that case.
My pseudocode also uses bad variable names (semi-intentionally). I expect better from your code.
1.2 Examples
As an example of what this function does:
>>> perm_gen_lex(”)
[”]
>>> perm_gen_lex(‘a’)
[‘a’]
>>> perm_gen_lex(‘ab’)
[‘ab’, ‘ba’]
>>> perm_gen_lex(‘abc’)
[‘abc’, ‘acb’, ‘bac’, ‘bca’, ‘cab’, ‘cba’]
>>> perm_gen_lex(‘abcd ‘)
[‘abcd’, ‘abdc’, ‘acbd’, ‘acdb’, ‘adbc’, ‘adcb’, ‘bacd’, ‘badc’, ‘bcad’,
‘bcda’, ‘bdac’, ‘bdca’, ‘cabd’, ‘cadb’, ‘cbad’, ‘cbda’, ‘cdab’, ‘cdba’,
‘dabc’, ‘dacb’, ‘dbac’, ‘dbca’, ‘dcab’, ‘dcba ‘]
Note: For a string with n characters, your program will return a list containing n! strings. This will grow very
quickly. If your string contained every lowercase letter a to z (26 letters), the resulting list of permutations would
have 403,291,461,126,605,635,584,000,000 ≈ 4.03 × 1026 elements. If you want your code to finish in your lifetime,
you should probably stick to shorter strings for testing.
2 Base Conversion
2.1 Specification
One algorithm for converting a base 10 number to base b involves repeated division by the base b. Initially, one
divides the number by b. The remainder from this division is the units digit (the rightmost digit) in the base b
representation of the number (it is the part of the number that contains no powers of b). The quotient is then
divided by b on the next iteration. The algorithm stops when the quotient is 0.
CPE 202 Assignment 1, Page 3 of 5
Note that at each iteration, the remainder from the division is the next base b digit from the right—that is, this
algorithm fins the digits for the base b number in reverse order.
Here is an example for converting the base 10 number 30 into base 4:
quotient
remainder
1/4 7/4 30/4
0 1 7
1 3 2
Start here
So, 30 (base 10) ≡ 132 (base 4).
Think about how this is recursive in nature.
• For what values do I know the answer without doing any work?
• How can I turn the problem into a smaller problem?
In a file named base_convert.py, write a recursive function named convert that will take a non-negative integer
in base 10 and a target base (an integer between 2 and 16 inclusive) and returns a string representing the number in
the given base.
def convert(num: int, base: int) -> str:
“””Returns a string representing num in the given base.
Implemented recursively.
“””
2.2 Examples
As some examples:
>>> convert(30, 4)
‘132’
>>> convert(45, 2)
‘101101’
>>> convert(316, 16)
’13C’
Note that for bases > 10, the symbols used for 10, 11, 12, 13, 14, and 15 are A, B, C, D, E, and F respectively.
3 A Teddy Bear Picnic
3.1 Specification
This question involves a game with teddy bears. The game starts when I give you some bears. You can then
repeatedly give back some bears, but you must follow these rules (where n is the number of bears that you currently
have):
CPE 202 Assignment 1, Page 4 of 5
1. If n is even, then you may give back n/2 bears.
2. If n is divisible by 3 or 4, then you may multiply the last two digits of n together and give back this many
bears.
3. If n is divisible by 5, then you may give back 42 bears.
The goal of the game is to end up with EXACTLY 42 bears.
For example, suppose that you start with 250 bears. Then you could make these moves:
• Start with 250 bears.
• Since 250 is divisible by 5, you may return 42 of the bears, leaving you with 208 bears.
• Since 208 is even, you may return half of the bears, leaving you with 104 bears.
• Since 104 is even, you may return half of the bears, leaving you with 52 bears.
• Since 52 is divisible by 4, you may multiply the last two digits (resulting in 5 ∗ 2 = 10) and return these 10
bears. This leaves you with 42 bears.
• 42 bears is the goal! So, we succeeded!
Note that at several of the steps, we had several options for how to proceed; not all of them would have resulted in
success.
In a file named bears.py, write a recursive function named bears to the following specification:
def bears(n: int) -> bool:
“””Returns whether it is possible to win the bear game starting with
n bears.
Implemented recursively.
“””
Although this problem may seem silly at first, it’s an example of a reachability problem, which is a problem that
arises in many areas of computer science.
3.2 Examples
Some examples:
>>> bears(250) # We saw this above
True
>>> bears(42) # This is true because we’re already at the goal.
True
>>> bears(40)
False
>>> bears(53)
False
CPE 202 Assignment 1, Page 5 of 5
4 Testing
For each part, you are required to achieve 100% test coverage. This means that every line of code in your functions
must be executed at some point in at least one of your tests.
As discussed in the syllabus, when I grade your code, you will ordinarily receive feedback regarding any tests that
fail, unless you do not have 100% test coverage. In the event you do not have 100% test coverage, the only feedback
you will receive is that you need to do more testing. I don’t want you using my grading script to do your testing in
the last day.
5 GitHub Submission
Push your finished code back to GitHub. Refer to Lab 0, as needed, to remember how to push your local code.
