Python: 实现全组合

全组合

对于字符串abc，其全组合为a,b,c,ab,ac,bc,abc（也可以说空集包含在全组合中）。

思路

全组合可以直接使用循环或递归得出，但这里介绍一种使用位运算高效率求解全组合的方法。

对于一个如长度为3的字符串abc，其全组合实际上可以用以abc共3个位置上是否“显示”来得到，比如a c就是b不显示，而很容易发现这种“显示”与“不显示”可以用二进制表示，即从000（空集）到111（abc）来表示。而111则为十进制数2^3-1的值，这样思路就很清晰了。

代码

def combinations(str):
    n=1<<len(str)
    for i in range(n):
        bits=[i>>offset&1 for offset in range(len(str)-1,-1,-1)]
        current=[str[index] for (index,bit) in enumerate(bits) if bit==1]
        print(''.join(current));

运行

combinations('abcd')

结果：

d
c
cd
b
bd
bc
bcd
a
ad
ac
acd
ab
abd
abc
abcd