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
请问如何去掉抽取一个的组合,就是说我不要a这样单个的组合。