I'm stuck in PS6 problem #4 how do you make all possible subsets of the hand?
MIT 6.00 Intro Computer Science (OCW)
Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
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)
def produce_all_possible_combinations( hand, letterPos, combinations, possible):
if letterPos == 0:
a = 
b = 
possible += hand [i]
combinations = a + b
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
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
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.
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.