Combinatorics: Pure Python Power Set algorithm implementation. Generator returns power set elements (permutation), in ascending order from smaller to bigger subsets.

power_set.py

'''
Use `python -m doctest power_set.py` for tests.

Usage:
    >>> ps = power_set([1,2,3])
    >>> for ss in ps:
            print(ss)
Output:
    [], 
    [1], 
    [2], 
    [3], 
    [1, 2], 
    [1, 3], 
    [2, 3], 
    [1, 2, 3]

More information about Power Set: https://en.wikipedia.org/wiki/Power_set
'''


def _product(ones, source_set):
    '''
    Return subset of the source_set, built from elements with indices
    represented by list "ones"

    >>> _product([0, 1, 2], [1, 2, 3, 4, 5, 6])
    [1, 2, 3]
    >>> _product([], [1, 2, 3])
    []
    >>> _product([3, 4], [1, 2, 3])
    Traceback (most recent call last):
     ...
    IndexError: list index out of range
    >>> _product([1], [1,2,3])
    [2]
    '''
    # # Canonical implementation
    # l = len(ones)
    # out = [None] * l
    # for i in range(0, l):
    #     out[i] = source_set[ones[i]]
    # return out

    # One-liner
    return list(map(lambda i: source_set[i], ones))

def _most_significant(ones, source_setlen):
    '''
    Find the most significant digit and return it's place in "ones" list. -1 means full overflow.

    >>> _most_significant([2,3,4], 5)
    -1
    >>> _most_significant([0,1,3], 5)
    2
    '''
    k = len(ones) - 1
    while ones[k] == (source_setlen - 1) - (len(ones) - 1 - k):
        k -= 1
    return k


def power_set(source_set):
    '''
    Generator returns the power set elements from the source_set list sorted by ascending
    the size of the power set element, excluding duplicates.

    >>> list(power_set([1, 2, 3]))
    [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
    >>> list(power_set([1, 2]))
    [[], [1], [2], [1, 2]]
    >>> list(power_set([1, 2, 3, 4]))
    [[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
    '''
    l = len(source_set)

    # yield trivial case
    yield []

    for setlen in range(1, l + 1):
        # # initial
        # ones = [None] * setlen  # build empty list to store element indices
        # for i in range(0, setlen):  # fill the subset with ascending indices
        #     ones[i] = i

        # oneliner
        ones = list(range(0, setlen))

        yield _product(ones, source_set) # yield trivial case

        if setlen == l:  # reached the biggest set (the source_set itself)
            return

        last_digit = setlen - 1  # pointer to "less significant digit",
                                 # the last element of indices list

        while True:
            ones[last_digit] += 1 # increment the "less significant digit" (LSD)

            if ones[last_digit] > l-1: # check for decimal place overflow
                # LSD to point to last element of source set
                ones[last_digit] = l-1
                # 1) find most significant digit (MSD)
                k = _most_significant(ones, l)
                if k == -1: # 2) check for full overflow
                    break
                # 3) increment MSD
                ones[k] += 1

                # 3) update remaining digit places
                for i in range(k+1, setlen):
                    ones[i] = ones[i-1] + 1

            yield _product(ones, source_set)