A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

Working on Problem Set 6 problem 4, it is required to generate all subsets of a list. The easiest way is to recursive in my understanding. If I can generate all subsets of a list without the first element (that's list[1:]), and store it in a container, then iterate through the container A, and combine the first element, then store the combined result in container B. Container A and B all together should be the result. I have great difficulty to implement this. I think I don't learn python well enough to write the code ... Anybody help me out!

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

    I googled, and found the following code works. But I can't understand why it is so... def subsets(x): if x == []: return [[]] else: s = [x] for elem in x: tmp = x[:] tmp.remove(elem) new_sub = subsets(tmp) for y in new_sub: # <-- can't just make it a set(), because lists aren't hashable. if y not in s: s.append(y) return s

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

    i pasted your code to dpaste... it is here http://dpaste.com/535552/ sometimes its hard to wrap your head around a recursive algorithm at line 6 it starts a loop. line 8 removes an element from the list. then line 9 calls the function (itself) with the new list. this is the first 'instance' of the function and it just gets paused at line 9 till the recursions all get done. so at line 9 when it calls itself a new instance of of the function runs lines 2-9 again. this keeps happening until finally there aren't any elements left in the list and lines 2,3 return without calling itself again. at this point the very last instance has returned an empty list and - whoops the next line didn't work for the empty list hmmm... i passed a list to the function, maybe it was expecting something else. at least that is how it looks like it was meant to work. i tried it and it didn't work so i put some print statements in to try to see what is happening - the print statements might help understand the recursion part.. http://dpaste.com/535569/ don't put to many elements in the list, it will print a lot.!!

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

    "Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion." from this wipedia article: http://en.wikipedia.org/wiki/Recursion i like the parallel mirror analogy.

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

    http://en.wikipedia.org/wiki/Recursion_(computer_science)

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

    i put a try/except statement in to handle the null list just to get it to continue and see what it prints out/ also took the list down to 3 elements to lessen the recursions http://dpaste.com/535605/

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

    Thanks a lot. I have finally worked it out, after i post this question. I will paste later on.

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