A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 5 years ago
I am having trouble generating all the possible submultisets of the letters in a hand for problem#4 in ps6. Can anyone give me a hint?
anonymous
 5 years ago
I am having trouble generating all the possible submultisets of the letters in a hand for problem#4 in ps6. Can anyone give me a hint?

This Question is Closed

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0If 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..k1. 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..k1, the sets from 0..k will be the same list of sets, and the same sets with the kth 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 jth letter will be included in this kth subset only if the jth bit is set in the binary form of the number k. You can test this with if (k & (1<<j)) != 0: # add the jth letter to this_subset # loop finished, add this_subset to list of subsets This feels like a more Cstyle solution, but it works very well. If you aren't familiar with the bittwiddling operators, 1<<j is a binary number with only the jth bit set. & is a bitwise and, so k&(1<<j) will be either 0 (if the jth bit of k is not set) or (1<<j) if it is set.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Wow that really helps a lot!! Thanks so much!!
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.