Python 3 def powerset (A) \" \" \"Build the powerset of A Given a set A, the pow

Question

Python 3

def powerset (A) " " "Build the powerset of A Given a set A, the powerset of A is the set of all subsets of A. Hint: recursion, anyone? no, really, you need to use recursion Hint: there are two base cases to the recursion: see lecture for the way to think about powerset recursively first base case: size of A is 0 second base case: size of A is 1 Hint: when you are changing a list, cloning makes it safer Hint: you may not want to test this function on a set of size 40, unless you are very patient, are not concerned about the due date, and have a lot of spare cash for memory upgrades (if that is not clear, watch the Eames video again) >>powerSet (C1,2]) C], 011, C2], C1,21] Params: A (list): finite set of integers, represented internally as a list Returns: (list) powerset of A, represented internally as a list

Explanation / Answer

Here we need to generate the power set of a given set.

what is power set?

A power set is the set of all subsets.

For example., power set of {1,2,3} = {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

How to generate power set?

We can do it by recursion. Observe the generation of power sets.

Size of set

Set

Power set

0

{}

{}

1

{a}

{}
{a}

2

{a,b}

{}

{a}

{b},{a,b}

3

{a,b,c}

{}

{a}

{b},{a,b}

{c},{a,c},{b,c},{a,b,c}

4

{a,b,c,d}

{}

{a}

{b},{a,b}

{c},{a,c},{b,c},{a,b,c}

{d},{a,d},{b,d},{a,b,d},{c,d},{a,c,d},{b,c,d},{a,b,c,d}

5

{a,b,c,d,e}

{}

{a}

{b},{a,b}

{c},{a,c},{b,c},{a,b,c}

{d},{a,d},{b,d},{a,b,d},{c,d},{a,c,d},{b,c,d},{a,b,c,d}

{e},{a,e},{b,e},{a,b,e},{c,e},{a,c,e},{b,c,e},{a,b,c,e},{d,e},{a,d,e},{b,d,e},{a,b,d,e},{c,d,e},{a,c,d,e},{b,c,d,e},{a,b,c,d,e}

Could you find some pattern in it? what is the pattern or how is recursion involved here?

It is so simple, if you could generate powerset for lesser size(i.e., size-1) then the powerset for original size is just union of powerset of size-1 and set generated by appending the last element to the each element of previous power set.

let’s take example size = 3, set = {a,b,c}

for set ={a,b} power set = {{},{a},{b},{a,b}}

when you append c, then the power set = union({{},{a},{b},{a,b}}, {{c},{a,c},{b,c},{a,b,c}})

So In order to write code, generate power set form 2nd element to last element and return the union of previous power set and append the first element to each of the previous power set generated.

Python code for generation of power set:

def powerset(A):

   if A:

       prev = powerset(A[1:])

       return prev + [[A[0]] + x for x in prev]

   return [[]]

#Call powerset with a set.

Size of set

Set

Power set

0

{}

{}

1

{a}

{}
{a}

2

{a,b}

{}

{a}

{b},{a,b}

3

{a,b,c}

{}

{a}

{b},{a,b}

{c},{a,c},{b,c},{a,b,c}

4

{a,b,c,d}

{}

{a}

{b},{a,b}

{c},{a,c},{b,c},{a,b,c}

{d},{a,d},{b,d},{a,b,d},{c,d},{a,c,d},{b,c,d},{a,b,c,d}

5

{a,b,c,d,e}

{}

{a}

{b},{a,b}

{c},{a,c},{b,c},{a,b,c}

{d},{a,d},{b,d},{a,b,d},{c,d},{a,c,d},{b,c,d},{a,b,c,d}

{e},{a,e},{b,e},{a,b,e},{c,e},{a,c,e},{b,c,e},{a,b,c,e},{d,e},{a,d,e},{b,d,e},{a,b,d,e},{c,d,e},{a,c,d,e},{b,c,d,e},{a,b,c,d,e}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.