Bitwise Techniques for Subset Iterations in Python. Code for blog post https://fishi.devtail.io/weblog/2015/05/18/common-bitwise-techniques-subset-iterations/

power_set.py

#!/usr/bin/env python3
 
"""
Iterate over each subset of any size (Power set)
"""
def power_set(A): 
    subsets = []
    N = len(A)

    # iterate over each subset
    for mask in range(1<<N):
        subset = []
        for n in range(N):
            if ((mask>>n)&1) == 1:
                subset.append(A[n])

        subsets.append(subset)

    return subsets

if __name__ == '__main__':
    A = [4,5,7]

    # print subsets
    for subset in power_set(A):
        print(subset)

subsets_eq_k.py

#!/usr/bin/env python3
 
"""
Iterate over subsets of size exactly K
"""
def subsets_eq_k(A,K):
    subsets = []
    N = len(A)

    # iterate over subsets of size K
    mask = (1<<K)-1     # 2^K - 1 is always a number having exactly K 1 bits
    while mask < (1<<N):
        subset = []
        for n in range(N):
            if ((mask>>n)&1) == 1:
                subset.append(A[n])
 
        subsets.append(subset)
 
        # catch special case
        if mask == 0:
            break
 
        # determine next mask with Gosper's hack
        a = mask & -mask                # determine rightmost 1 bit
        b = mask + a                    # determine carry bit
        mask = int(((mask^b)>>2)/a) | b # produce block of ones that begins at the least-significant bit

    return subsets
 
if __name__ == '__main__':
    A = [4,5,7,9]
    K = 2

    # print subsets
    for subset in subsets_eq_k(A,K):
        print(subset)

subsets_leq_k.py

#!/usr/bin/env python3
 
"""
Iterate over subsets of sizes less or equal K
"""
def subsets_leq_k(A,K):
    subsets = []
    N = len(A)
 
    # iterate over subsets of size less or equal K
    mask = 0
    while mask < (1<<N): 
        subset = []
        for n in range(N):
            if ((mask>>n)&1) == 1:
                subset.append(A[n])
 
        subsets.append(subset)
 
        # catch special case when K is zero
        if K == 0:
            break
 
        # determine next mask
        if bin(mask).count("1") < K:
            mask += 1
        else:
            mask = (mask|(mask-1))+1

    return subsets 
 
if __name__ == '__main__':
    A = [4,5,7,9]
    K = 3

    # print subsets
    for subset in subsets_leq_k(A,K):
        print(subset)