CSC148 - Lab 4
Permutations and Subsets
Download subsets_perms.py.
Your goal will be to fill in the code for the methods all_subsets and all_perms.
all_subsets, when called, should print all the subsets of a given list. For example, here are all the subsets of the list [1,2,3]:
[]
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]
The order in which you output the subsets does not matter, but none should be repeated.
The method has been defined to take 3 parameters: items, subset, and i. items is the list you are taking all subsets of, subset is the subset you are constructing, and i is the index into items indicating which element of items you are considering for membership into subset. You should consider the two cases of adding items[i] to subset or not, and make appropriate recursive calls. Calling all_subsets([1,2,3],[],0) should output all of the subsets listed above. How many subsets should be output?
all_perms, when called, should print all the permutations of items. For example, here are all the permutations of the list [1,2,3]:
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
The order in which you output the permutations does not matter, but none should be repeated.
The method in the starter code has been defined to take 3 parameters: items, used, and perm. items is the list you are building the permutations of, used is a list of boolean values indicating whether or not we have already used an element of items (used[i] == True if and only if items[i] is in perm), and perm is the permutation we are constructing. You should attempt to add each element of items (such that used[i] == False) to the end of perm, and then appropriate recursive calls. For example, calling all_perms([1,2,3],[False,False,False],[]) should result in the sample output given above. How many permutations should be output?
Write a few tests for both these methods (what should they output if items == []? len(items) == 1?).
Duplications
What happens if these two methods are called with duplicate elements? What does all_subsets([1,1,1], [], 0) output?
Modify both of these methods so that even if items are duplicated in items, each distinct subset/permutation is output only once. For simplicity, you may assume that items will be sorted in increasing order. Test the methods out for various values. How many subsets/permutations should be output when there are duplicate elements?