Question

I am having trouble generating all the possible sub-multisets of the letters in a hand for problem#4 in ps6. Can anyone give me a hint?

Answer 1

If there are n letters in your hand there will be 2**n subsets.

Half of them will include the first letter, the other half will omit it (and so on for all letters.) So one way is to create a recursive function which will generate all the subsets starting using letters from 0..k given a list of the subsets using letters from 0..k-1. At the bottom of your recursion, the subsets from 0..0 are "" and hand[0] (either the empty string or a string with the first letter.) Given the list of subsets using letters from 0..k-1, the sets from 0..k will be the same list of sets, and the same sets with the k-th letter added to each one.

Alternately, you can do this completely iteratively by stepping through the 2**n possibilities as in

subsets = [ ]
for k in range(2**n):
this_subset = ""

Then decide that the j-th letter will be included in this k-th subset only if the j-th bit is set in the binary form of the number k. You can test this with
if (k & (1<<j)) != 0:
# add the j-th letter to this_subset
# loop finished, add this_subset to list of subsets

This feels like a more C-style solution, but it works very well. If you aren't familiar with the bit-twiddling operators, 1<<j is a binary number with only the j-th bit set. & is a bitwise and, so k&(1<<j) will be either 0 (if the j-th bit of k is not set) or (1<<j) if it is set.

Answer 2

Wow that really helps a lot!! Thanks so much!!