Question

Write a Python function powerSet() that takes in a finite list object AA and returns P(A)P(A),...

Write a Python function powerSet() that takes in a finite list object AA and returns P(A)P(A), the power set of A. The output should be only in the form of list objects.


Note: Make sure you are familiar with some of Python's basic built-in list functions and operators, as they will make completing this problem far easier.

For example:

Test Result
A = [0, 1, 2]

output = set([frozenset(a) for a in powerSet(A)])
expected = [[], [0], [0, 1], [2], [1], [0, 2], [1, 2], [0, 1, 2]]
expected = set([frozenset(a) for a in expected])

print (output==expected)
True
A = ['a', 'b', 'c', 'd']

output = set([frozenset(a) for a in powerSet(A)])
expected = [[], ['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']]
expected = set([frozenset(a) for a in expected])

print (output==expected)
True

I will upvote! If code actually works in Python.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Below is the code:

'''
The function takes a set as parameter
and returns its power set
'''
def powerSet(A):
size = len(A) #calculating length of A
pow_set_size = 2**size #calculating size of power set
counter = 0
power_set = [] #initialize power set as empty list
  
# Run from counter 00...000 to 11...111 i.e 0 to 2**n - 1
for counter in range(0, pow_set_size):
set = []
# loop over from lsb to msb
for i in range(0, size):
if((counter & (1 << i)) > 0): #checking if the ith bit is 1
set.append(A[i]) #adding the element to the subset
power_set.append(set) #adding the subset to the power set
  
return power_set;
  
A = [0, 1, 2]
output = set([frozenset(a) for a in powerSet(A)])
expected = [[], [0], [0, 1], [2], [1], [0, 2], [1, 2], [0, 1, 2]]
expected = set([frozenset(a) for a in expected])
print (output==expected)

Code Screenshot:

Output:

Explanation:

  • The number of elements in a power set of set A is equal to 2n, where n is the size of set A.
  • So we take a variable counter and loop from 0 to 2n - 1.
  • Now we for a counter value, we check if it has ith bit set or not. If the ith bit is set, we add that element to a subset
  • Finally, we add all our subsets to get our power set.
  • Below is an example for A = [0,1,2]

n = 3 , therefore size of power set = 23 = 8

Counter Value                  Subset
    000         -->            [] #empty set
    001         -->            [0]
    010         -->            [1]
    011         -->            [0,1]
    100         -->            [2]
    101         -->            [0,2]
    110         -->            [1,2]
    111         -->            [0,1,2]

===========================

If you find my answer helpful, please up-vote it.

For any queries, ask in comment section. Thank you.

Add a comment
Know the answer?
Add Answer to:
Write a Python function powerSet() that takes in a finite list object AA and returns P(A)P(A),...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Write a Python function cardinality() that takes in three Python set objects, representing sets of between...

    Write a Python function cardinality() that takes in three Python set objects, representing sets of between 0 and 50 integers, AA, BB, and UU. Your function should return a single non-negative integer value for the cardinality of the set below. AA and BB are subsets (not necessarily proper) of the universal set UU. |P(A¯¯¯¯∩B)||P(A¯∩B)| Note 1: You can copy-paste the code declaring the various visible test cases below. We strongly encourage you to do this to test your code. Note...

  • Use the FDR to design and write a function, maxValTimes, that takes a list of integers...

    Use the FDR to design and write a function, maxValTimes, that takes a list of integers and returns a set containing the value(s) that occur the same number of times as the maximum value in the list. If the list is empty, return an empty set.   For example if the list was [2,1,1,2,3,3,1] the function would return {2,3} as the maximum value is 3 which occurs twice, and 2 also occurs twice (but 1 occurs 3 times). For full marks,...

  • write a Python function that takes in a list of integers and returns maximum and minimum values in the list as a tuple

    1 write a Python function that takes in a list of integers and returns maximum and minimum values in the list as a tuple. Hint (can be done in one pass, you are not allowed to use built-on min and max functions.)max, min = find_max_min(my_list):2 write a Python function that takes in a list of integers (elements), and an integer number (num). The functions should count and return number of integers in elements greater than, less than, and equal to...

  • Python Question? Write a function called reverse(user_list, num = -1) that takes a list and a...

    Python Question? Write a function called reverse(user_list, num = -1) that takes a list and a number as parameters. The function returns a copy of the list with the first number of items reversed. Conditions: The number parameter must be a default argument. -      If the default argument for number is given in the function call, only the first number of items are reversed. -      If the default argument for number is not provided in the function call, then the...

  • Python homework Write a function called insert_value(my_list, value, insert_position) that takes a list, a value and...

    Python homework Write a function called insert_value(my_list, value, insert_position) that takes a list, a value and an insert_position as parameters. The function returns a copy of the list with the value inserted into the list (my_list) at the index specified by insert_position. Check for the insert_position value exceeding the list (my_list) bounds. if the insert_position is greater than the length of the list, insert the value at the end of the list. if the insert_position is less than or equal...

  • Python. Write a function that takes in a list and returns the first nonzero entry. def...

    Python. Write a function that takes in a list and returns the first nonzero entry. def nonzero(lst): """ Returns the first nonzero element of a list >>> nonzero([1, 2, 3]) 1 >>> nonzero([0, 1, 2]) 1 >>> nonzero([0, 0, 0, 0, 0, 0, 5, 0, 6]) 5 """ "*** YOUR CODE HERE ***"

  • Using Python Programming Language: 3. Write a function flatten that takes a 2D list and returns...

    Using Python Programming Language: 3. Write a function flatten that takes a 2D list and returns all the items of each list concatenated together into one new 1D list. For example: flatten ([["a", "b"],["c","0"],["e","f"]]) would return ["a", "b","C","d", "e","f"] Save the function in a PyDev library module named functions.py Write a program t03.py that tests flatten function and prints the returned flat list to the screen. Test your program with a different list, hardcoded in t03.py • Copy the results...

  • Use Python WingPersonal to compile and also please give output Math and String operations Write a...

    Use Python WingPersonal to compile and also please give output Math and String operations Write a script to perform various basic math and string operations. Use some functions from Python's math module. Generate formatted output. Basic math and string operations Calculate and print the final value of each variable. a equals 3 to the power of 2.5 b equals 2 b equals b + 3 (use +=) c equals 12 c = c divided by 4 (use /=) d equals...

  • Please write a python function for : greedy: This function takes two inputs: one a graph,...

    Please write a python function for : greedy: This function takes two inputs: one a graph, and the other an ordering of the vertices as a list, and returns the proper vertex-coloring produced by the greedy algorithm over the ordering in the list. Examples: greedy({"A" : ["B", "C"], "B" : ["A"], "C" : ["A"]},[“A”, “B”, “C”]) should return {“A” : 1, “B” : 2, "C" : 2} greedy({“A” : ["B"], "B" : [“A”, “C”],"C" : [“B”, “D”), “D" : ["C"]},[“A”,...

  • Write a function isaset which takes a list of any equality type2 and returns true if...

    Write a function isaset which takes a list of any equality type2 and returns true if the list is a set (each element appears exactly once). So, the type of isaset is ' 'a list -> bool. Hints: • Do not try for efficiency. A brute-force O(n2 ) solution is appropriate to this exercise. 3 • You might find it easier to develop an algorithm if you consider how to determine the list is not a set. • A recursive...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT