Set of all subsets

Question

In Python2 I could use

def subsets(mySet):
    return reduce(lambda z, x: z + [y + [x] for y in z], mySet, [[]])

to find all subsets of mySet. Python 3 has removed reduce.

What would be an equally concise rewrite of this for Python3?

Answer 1

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!

Answer 2

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