Python list all subsets

The Subsets (Powerset) of a Set in Python 3

Looking at recursive, iterative, and other implementations to compare their performance

The first time I thought of this problem was when I worked on testing a component on a work-related project. Back then, I’ve realized that for properly testing the component, I should generate what seemed to be 2ⁿ distinct cases (n being the number of element types). 2ⁿ…odd coincidence or what?

After some thought, I realized this was a general answer, as these are the number of subset types that you can generate from a set with n element types. I said types so many times because I want to underline I’m looking at the possible test signature, regardless of the content.

Let’s say we have a function, f, which needs three parameters (three is a must, we’ll account for that with an assert). How many possibilities do we have if we allow None (or null depending on the programming language) as input? None (or null) is a generic type, usually assigned for objects which, in object-oriented programming languages (like Python or Java) is something common to all standard types (that’s because the standard types usually inherit some primitive object like ‘Object’). The answer is 8 because we either put some content in some parameter or we don’t ⇔ 0 or 1 so 2ⁿᵘᵐᵇᵉʳ ᵒᶠ ᵖᵃʳᵃᵐᵉᵗᵉʳˢ.

I will be working with Python3, using generators (because of that exponential I want to save the memory). Fortunately, there are multiple ways to generate the powerset of a set (as it’s usually called). It’s quite interesting to see the differences. Overall we have:

1. Recursive implementation I;
2. Recursive implementation II;
3. Iterative implementation;
4. Using chain and combinations from itertools.

Recursive implementation I

I really like this one (probably because it’s the only one I drafted top to bottom, the others being, with a little retouch, gathered). On this one, I thought in an induction-like manner…This problem, of size n it’s the same as its smaller cousin, of size n-1, plus something. I think it’s a nice way of using backward recursion, building the solutions as we exit from the recursive call.

I want to emphasize a point. This solution has, although ‘hidden’, the idea that’s used in all the recursive implementations — that is, the full solution S([H|T])=[H|S(T), S(T)] (H — being the head element of the initial list, T being the tail (the rest of the elements from the list)). For those with a Prolog background, this should look very intuitive.

Looking at the code below you might ask, where do we concatenate these two solutions (the one with H and the one without it). The answer is in the for loop, taking into account the yield [] part.

def classical_recursive_one(elems): 
yield [] # first return the result we’re sure about 
for i in range(len(elems)): 
for x in classical_recursive_one(elems[i+1:]): 
# induction part 
yield [elems[i]] + x sth = [‘neigh’, ‘category’, ‘purpose’]
for x in classical_recursive(sth): 
print(x)

[] 
['neigh'] 
['neigh', 'category'] 
['neigh', 'category', 'purpose'] 
['neigh', 'purpose'] 
['category'] 
['category', 'purpose'] 
['purpose']

Recursive implementation II

This one uses backward recursion again, and the idea is that the solution is constructed either by taking the element at the current position or not:

def classical_recursive_two(elems): 
""" Given a list of elements return a generator 
that will generate all the subsets """ 
if len(elems) yield elems 
yield [] 
else: 
for item in classical_recursive_two(elems[1:]): 
yield [elems[0]] + item 
yield itemsth = [‘neigh’, ‘category’, ‘purpose’]
for x in classical_recursive_two(sth): 
print(x)

['neigh', 'category', 'purpose'] 
['category', 'purpose'] 
['neigh', 'purpose'] 
['purpose'] 
['neigh', 'category'] 
['category'] 
['neigh'] 
[]

I will explain the else part. That’s where all the fun is. That reflects the two decision branches I’ve spoken about above when constructing solutions. So for all the possible solutions of the subproblem (this is why the for is needed), construct the two NEW possible solutions via 2 yields. Easy peasy…

Iterative implementation

This is the old-school way to do it. It’s elegant nonetheless. It uses the incredible property 😄 that all numbers from 1 up to 2ⁿ are distinct. If we would write those numbers in base 2…those 1 and 0 bits could be interpreted like: „Take the element from the list if 1, don’t take it if 0”. But hey, we can actually do this with some BIT operations magic:

def classical_iterative(elems): 
powerset_size = 2**len(elems) 
counter = 0 
j = 0 
 
for counter in range(0, powerset_size): 
results = [] 
for j in range(0, len(elems)): 
# take the element if on bit position j it says to take it (i.e. 1 appears) 
if((counter & (1 0): 
results.append(elems[j]) 
yield results 

sth = [‘neigh’, ‘category’, ‘purpose’]
for x in classical_iterative(sth): 
print(x)

[] 
['neigh'] 
['category'] 
['neigh', 'category'] 
['purpose'] 
['neigh', 'purpose'] 
['category', 'purpose'] 
['neigh', 'category', 'purpose']

Using chain and combinations from itertools

This one is for the lazy of hand…it’s a smart use of itertools nonetheless. chain is used to treat multiple sequences as a single sequence and combinations to generate…all the possible combinations. What’s so special about this and how it’s related to our problem anyway. It just so happens that the sum of all the possible combinations up to n is actually 2ⁿ. This one is a mouthful and some time to actually appreciate this property is needed…essentially, if you don’t understand this solution, start by trying to understand this property:

from itertools import chain, combinationsdef powerset(iterable): 
"powerset([1,2,3]) → () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" 
s = list(iterable) 
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))sth = [‘neigh’, ‘category’, ‘purpose’]
for x in powerset(sth): 
print(list(x))

[] 
['neigh'] 
['category'] 
['purpose'] 
['neigh', 'category'] 
['neigh', 'purpose'] 
['category', 'purpose'] 
['neigh', 'category', 'purpose']

Performance comparison

Ok, now that we’ve sketched the solutions which one is actually faster. Let’s test it out:

import matplotlib.pyplot as plt
from time import timedef time_me(func, elems): 
start = time() 
# Because it's a generator we want to evaluate it 
list(func(elems)) 
end = time() 
return end - start 
 

def gather_times(func, min_value, max_value): 
times = [] 
print(f"Gathering running times for :") 
for value in range(min_value, max_value): 
test_elems = list(range(1, value)) 
times.append(time_me(func, test_elems)) 
print(times, '\n') 
return times
START = 3
STOP = 22
FIG_SIZE = (15, 10)funcs = [classical_recursive_one, classical_recursive_two, classical_iterative, powerset]
fig, axs = plt.subplots(2, 2, figsize=FIG_SIZE)
fig.suptitle('Perf. comparison on different sizes of the problem')
for i in range(2): 
for j in range(2): 
sol_func = funcs[i * 2 + j] 
sol_times = gather_times(sol_func, START, STOP) 
axs[i][j].bar(range(STOP-START), sol_times) 
axs[i][j].set(xlabel=sol_func.__name__) 
axs[i][j].set_xticks(range(STOP-START))

Please look at the y-axis of every plot. You will see that although all methods have exponential running times (because the problem is of that nature), the powerset solution is the best one. In contrast, my method is almost the worst in terms of speed after the iterative one…Never mind, now we know which one to use in production.

Источник

Python program to get all subsets of set using Loops and Functions

The topic mainly deals with the concept of generating subsets of a given set.

This is important because, later on in advanced programming, it is helpful in implementing Dynamic Programming Solutions.

Python program to generate all possible subsets of a given set within a list

Moreover, a subset is defined as a part of a set or the whole set itself.

Let’s understand the concept with some examples and then implement it.

Output :[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Explanation of the Solution :

This program solution is described in many different ways Recursion, slicing, Itertools in python.
But this solution is based on simple loops and functions.

We know there are (2^n) subsets for a set of n elements.

Moreover, this solution is based on a simple idea :

Convert the numbers 0 to (2^n-1) into binary numbers, where n is the length of list
Now represent the binary equivalents in (n number of bits)
ex: a=[1, 2, 3, 4], n=4
0: (0) : (0000)
1: (1) : (0001)
7: (111) : (0111) and so on
Certainly, there is now a Binary list of elements represented in n bits.

Now traverse every digit in the sub list and append those values which are 1 and exclude those which are 0.

Let’s jump on to code what we have learned above,

def decimalToBinary(n): # converting decimal to binary b = 0 i = 1 while (n != 0): r = n % 2 b+= r * i n//= 2 i = i * 10 return b def makeList(k): # list of the binary element produced a =[] if(k == 0): a.append(0) while (k>0): a.append(k % 10) k//= 10 a.reverse() return a def checkBinary(bin, l): temp =[] for i in range(len(bin)): if(bin[i]== 1): temp.append(l[i]) return temp l =[1, 2, 3] binlist =[] subsets =[] n = len(l) for i in range(2**n): s = decimalToBinary(i) arr = makeList(s) binlist.append(arr) for i in binlist: k = 0 while(len(i)!= n): i.insert(k, 0) # representing the binary equivalent according to len(l) k = k + 1 for i in binlist: subsets.append(checkBinary(i, l)) # print(binlist) print this for more understanding print(subsets)

Output : [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

This is how the subsets can be produced using basic loops and functions in Python.

I hope this is pretty much clear to implement the concept regarding subsets.

Источник

Subsets in Python

Suppose we have a set of numbers; we have to generate all possible subsets of that set. This is also known as power set. So if the set is like [1,2,3], then the power set will be [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

• We will solve this using recursive approach. So if the recursive method name is called solve(), and this takes the set of numbers (nums), temporary set (temp), res and index
• The solve() function will work like below −
• if index = length of nums, then create a list same as temp, and insert into res and return
• temp[index] := 0
• solve(nums, temp, res, index + 1)
• temp[index] := 1
• solve(nums, temp, res, index + 1)
• The main function will be like below −
• res := an empty list
• create temp list of size same as the nums, and fill this with 0
• call solve(nums, temp, res, 0)
• main_res := an empty list
• for all lists in temp_res
  • temp := empty list
  • for i := 0 to length of lists
    • if lists[i] = 1, then insert nums[i] into temp

    Let us see the following implementation to get better understanding −

    Example

    class Solution(object): def subsets(self, nums): temp_result = [] self.subsets_util(nums,[0 for i in range(len(nums))],temp_result,0) main_result = [] for lists in temp_result: temp = [] for i in range(len(lists)): if lists[i] == 1: temp.append(nums[i]) main_result.append(temp) return main_result def subsets_util(self,nums,temp,result,index): if index == len(nums): result.append([i for i in temp]) #print(temp) return temp[index] = 0 self.subsets_util(nums,temp,result,index+1) temp[index] = 1 self.subsets_util(nums, temp, result,index + 1) ob1 = Solution() print(ob1.subsets([1,2,3,4]))

    Input

    Output

    [[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 3, 4]]

    Источник