A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

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?

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

    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.

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

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

  3. 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.