Set of all subsets

Here's a list of several possible implementations of the power set (the set of all subsets) algorithm in Python. Some are recursive, some are iterative, some of them don't use reduce. Plenty of options to choose from!


The function reduce() can always be reaplaced by a for loop. Here's a Python implementation of reduce():

def reduce(function, iterable, start=None):
    iterator = iter(iterable)
    if start is None:
        start = next(iterator)
    for x in iterator:
        start = function(start, x)
    return start

(In contrast to Python's built-in version of reduce(), this version does not allow to pass in None as start parameter.)

Special-casing this code with the parameters you passed to reduce() gives

def subsets(my_set):
    result = [[]]
    for x in my_set:
        result = result + [y + [x] for y in result]
    return result

Tags:

Python

Set

Subset