A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

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

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  3. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  4. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks it worked!

  5. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.