生成字符串的组合（非排列）

Question

我尝试在Python中实现《编程面试揭秘》里的一个算法，代码如下，但似乎没有成功（第二版第99页）：

这个算法的想法是生成一个字符串的所有组合（而不是排列），比如如果你输入“wxyz”，你应该能得到“w, wx, wxy, wxyz, wxz, wy, wyz, wz...”等等。如果显示了wz，那么zw就不算有效的组合。

def doCombine(strng, out, length, level, start):
    for i in range(start, length):
        out.append(strng[i])
        print out
        if (i < length - 1):
            doCombine(strng, out, length, level +1, i + 1)
        out = out[:-1]

x = list()
target = "wxyz"
print doCombine(target, x, len(target), 0, 0)

这里可能出了什么问题呢？我得到的输出结果相当糟糕。

Answer 1

我用递归生成器重写了这个合并函数。输出的是一个迭代器。

def combine(s):
    length = len(s)
    def gen(start, prepending=[]): #recursive generator
        if start == length-1:
            yield prepending + [s[start]]
        else:
            for i in range(start,length):
                current = prepending + [s[i]] #save the current list for reusing
                yield current
                for els in gen(i+1,current):
                    yield els
    for v in gen(0):
        yield v

s = "wxyz"
for v in combine(s):
    print(v)

一下子可能不太容易理解。

同样的技巧也用在了连接生成器中：以函数式风格制作的连接函数。

另外，我在试图理解你函数的过程中稍微重构了一下你的代码。为了方便那些可能感兴趣的人，我把它放在这里，帮助理解。

def combine(s):
    out = []
    length = len(s)
    def loc(start):
        for i in range(start, length):
            out.append(s[i])
            print out
            if (i < length-1):
                loc(i+1)
            del out[-1]
    loc(0)

---

我做了一些效率计算。

使用从 out 中添加和删除元素的代码（这是对原始代码稍作修改以便作为生成器使用）比我在这个回答中提供的代码稍微快一些（我认为这是因为我在每次迭代中使用了 prepending + [s[i]]，这会在内存中创建一个新列表。而在同一个列表上进行添加和删除操作则更快）。

详细信息在这里： https://ideone.com/V3WIM

Answer 2

可以看看来自itertools模块的combinations()函数。

Answer 3

在你现在的代码中，试着把这一行 out = out[:-1] 改成 del out[-1]。这两种写法都会把 out 的最后一个元素去掉，但在你现在的代码里，out 是被重新赋值的，而不是在原来的列表上操作。这样一来，原始列表里的字符就永远不会被删除，这显然会对输出结果造成很大的影响。

做了这个修改后，输出结果是：

>>> print doCombine(target, x, len(target), 0, 0)
['w']
['w', 'x']
['w', 'x', 'y']
['w', 'x', 'y', 'z']
['w', 'x', 'z']
['w', 'y']
['w', 'y', 'z']
['w', 'z']
['x']
['x', 'y']
['x', 'y', 'z']
['x', 'z']
['y']
['y', 'z']
['z']
None