Python刷题：用二进制方式求集合S的全部子集（二进制）

题型叙述

有一个集合S，规定复印出其全部子集 ，子集元素用分号分隔 ，在其中集合S自身和空集NULL都觉得是集合S的子集。比如
，有一个集合S，它的內容为“S={"A", "B", "C"}” ，那麼该集合S的全部子集为“A,B,C ”、“A,B ” 、“AC
” 、“BC”
、“A ”、“B
” 、“C”
、“NULL ” 。

解题思路

先要思索如何把集合求子集这一实际操作与二进制联络起來
，最先能够明确，集合S、空集及其单独元素的子集非常容易明确 ，无需与二进制关系还可以轻轻松松获得
，剩下的子集的求得构思便是某一元素没有子集里时，剩下的全部元素为一个子集 ，随后先后是某2个元素没有子集里时剩下的元素为一个子集
，依此类推，就可以获得全部子集 。想到二进制的特性 ，一个比特位上要不是0
，要不就是1，那麼能够应用比特位意味着每一个元素 ，它的数值1时表明此元素在子集中 ，数值0时表明此元素没有子集中
，随后依据“题型
”中的事例，将集合S的全部子集用二进制表明出去 ，随后写成相匹配的十进制就可以见到相匹配的规律性了
。

答题编码

def print_sub(val, s):
    # 获得相匹配十位数的二进制位字符串数组
    bin_str = bin(val).replace('0b', '').rjust(len(s), '0')

    idx = 0
    is_null = True
    while idx < len(s):
        # 假如该比特位为1
，则复印相匹配的元素
        if bin_str[idx] == '1':
            if not is_null:
                print(',', end='')

            is_null = False
            print(s[idx], end='')

        idx  = 1

    if is_null:
        print('NULL', end='')

    print(';')


def func(s):
    # 应用二进制的方法获得全部元素都存有时的二进制表明方法相匹配的十进制数
    # 自然，还可以应用别的方法获得这一值
    val = 0
    for i in range(len(s)):
        val |= (1 << i)

    # 解析xml并打印每一个子集
    while val >= 0:
        print_sub(val, s)
        val -= 1


if __name__ == '__main__':
    collection = ['A', 'B', 'C', 'D']
    func(collection)

輸出：

A,B,C,D;
A,B,C;
A,B,D;
A,B;
A,C,D;
A,C;
A,D;
A;
B,C,D;
B,C;
B,D;
B;
C,D;
C;
D;
NULL;

汇总

求集合的子集 ，在Python中

itertools.combinations

题型及答题优化算法来源于：书本《Python程序员面试宝典》 。