Question

I'm stuck in PS6 problem #4 how do you make all possible subsets of the hand?

Answer 1

I had trouble with this as problem as well. I eventually came up with a recursive function that I only figured out after watching a few more lectures. It probably isn't the most efficient with the complexity at O(2^n) where n is the length of the hand, but it works.

def pick_best_word_faster(hand, points_dict):
possible = ''
combinations = []
combinations = produce_all_possible_combinations( hand, len(hand), combinations, possible)
return combinations

def produce_all_possible_combinations( hand, letterPos, combinations, possible):
if letterPos == 0:
a = []
b = []
a.append(possible)
possible += hand [i]
b.append(possible)
combinations = a + b
return combinations
without_letter = produce_all_possible_combinations(hand, letterPos - 1, combinations, possible)
possible += hand[i]
with_letter = produce_all_possible_combinations(hand, letterPos - 1, combinations, possible)
combinations = without_letter + with_letter
return combinations

The method get_best_word_faster calls on the method produce_all_possible_combinations with the following parameters:

hand = the hand in string form
len(hand) = the length of the hand to start initiate it at the last letter
combinations = an empty list which will contain all the possible combinations
possible = a string which will contain the possible word to be added to combinations

Answer 2

The method produce_all_possible_combinations first looks to see if it's at the last letter of the hand. If so it does both not add the letter to possible and adds it to combinations and adds the letter to possible and adds it to combinations.

If it's not at the last letter, it assigns the list without_letter to call on itself with the letter position subtracted by 1. Then then it assigns the list with_letter to call on itself with letter position subtracted by 1, but it adds the letter to possible.

Then it combines both with_letter and without_letter into combinations and returns it back to the original get_best_word_faster method.

This is a little hard to grasp at first, so just work your way through the methods and eventually you should understand. If you need any more help or clarification, let me know.

Answer 3

Once you watch the lectures on Dynamic Programming this will also become more clear. Sadly this problem can't be solved using dynamic programming because it doesn't have any constraints, but the layout for Dynamic Programming is very similar.

Answer 4

Thanks it worked!