Power Set generation in Python

Question

I am trying to generate power sets and add up the elements of the powerset. This is what i have done.

Example:

Given N=3,
S={1,2,3}
P(S) = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
answer = (1)+(2)+(3)+(1+2)+(1+3)+(2+3)+(1+2+3)
= 24

Sample I/O:

Input: 1 3

Output: 24

My code:

from itertools import combinations, chain

j = int(input())

for z in range(j):
    x = int(input())
    a_set = set()
    for m in range(x):
        a_set.add(m + 1)
    lst = []
    for q in chain.from_iterable(combinations(a_set, r) for r in range(len(a_set) + 1)):
        lst.append(sum(q))
    print(sum(lst))

I am getting the correct output but it takes more time to compute for larger numbers.

Input
First line has T, the total number of test cases.
The next T lines contains a number N in each line.

Output
T lines giving answer as defined in the question for each N.

Constraints
1<=T<=42
1<=N<=42

How to make it run faster. Thanks

If you just want the final total, there's no need to build the powerset: note that each element of your original set appears exactly 4 times, so the total is `4 * (1 + 2 + 3)`. More generally, if you have `n` elements in your original set, each element would appear in exactly `2**(n-1)` of the subsets in the powerset, so the general result would be `sum(my_set) * 2**(len(my_set) - 1)`. — Mark Dickinson, Sep 21 '14 at 17:33

Peter Pei Guo · Answer 1 · 2014-09-21T17:39:29.117

6

The answer is simply:

n * (n + 1) * 2 ** (n - 2)

There are 2 ** n elements in the power set, and each number appears exactly in half of them, so each number appear 2 ** (n - 1) times.

So the answer is: (1 + 2 + ... + n) * 2 ** (n - 1), which can be reduced to what is at the top of the answer.

Quite often, those math related questions are not about using brutal force, but to do the math first.

edited Sep 21 '14 at 17:39

answered Sep 21 '14 at 17:34

Peter Pei Guo

7,770
18
35
54

score 0 · Answer 2 · answered Dec 06 '18 at 14:27

################################################ Power set ########################################################
# The power set of a set is the set of all its subsets, or a collection of all the different combinations of items# 
#                               contained in that given set                                                       #
################################################################################################################### 
# 1) SET,is a collection of any number of unique objects whose order does not matter.                             #
# 2) The subset of a set is any combination (the null set included) of its members,                               #
#    such that it is contained inside the superset                                                                #
# 3) The length, or cardinality, of a power set is 2power(n)                                                      #
########################################### Algorithm #############################################################
# 1) Start with an empty set [] and its power set is []                                                           #
# 2) For every element inside the Set                                                                             #
#     a) Create a copy of every set in the current power-set                                                      #
# 3) Add the element to each one.                                                                                 #
# 4) Add the copies to the current power-set.                                                                     #
###################################################################################################################

import sys

def expand_power_set(set):
  cardinality=2**len(set)
  print("Cardinality of the power set is", cardinality)
  power_set=[[]]
  for element in set:
    # iterate over the sub sets so far
    for subset in power_set:
      # add a new subset consisting of the subset at hand added elem
      power_set=power_set+[list(subset)+[element]]
  return power_set


if __name__ == "__main__":
   #powerset =sys.argv
   #powerset =['a','b','c']
   powerset= [1,2,3]
   output = expand_power_set(powerset)
   print("Expand the power set:", output)

score 0 · Answer 3 · answered Apr 03 '19 at 05:08

I have added an answer with an explanation to generate the power set here. So, for a detailed explanation of the function go there.

def power_set(A):
    length = len(A)
    return {
        frozenset({e for e, b in zip(A, f'{i:{length}b}') if b == '1'})
        for i in range(2 ** length)
    }

Now, you can simply run the following:

>>> sum(sum(s) for s in power_set(S))
24

Power Set generation in Python

3 Answers3

Linked