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

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)

这里可能出了什么问题？我的输出结果相对较差。

- Rio

Answer 1

在您当前的代码中，尝试将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

- Andrew Clark

---

太棒了！我需要好好理解一下这个区别，但是谢谢！ - Rio

@Rio - 很高兴这篇文章对你有所帮助。至于理解差异，你原来的代码相当于完全删除了从列表中删除字符的那一行。由于 out 是可变的，你可以在 doCombine 中修改它，但是如果你将 out 重新分配给一个新值，调用者版本的 out 将不会改变。 - Andrew Clark

根据你的审美观，out.pop()可能是del out[-1]的一个稍微更漂亮的替代方案。 - John Y

有些人可能会担心“弹出的”值永远不会被分配到任何地方。但我承认这样写更美观。 - Guy

Answer 2

请查看itertools模块中的combinations()函数。

- hymloth

---

能不能不用itertools来实现呢？我对算法部分很感兴趣，PIE书中也讲得很清楚。只是我不太明白为什么它不能工作... - Rio

一般来说，是的。只需查看我提供的链接中的源代码即可。您想要实现的目标肯定无法使用您提供的代码实现。它似乎在做另一件事情。 - hymloth

@hymloth - Rio 提供的代码实际上非常接近一个可行的解决方案，详见我的回答。 - Andrew Clark

@Rio FWIW，itertools模块的文档包括每个工具的纯Python等效版本--算法是显而易见的 :-) - Raymond Hettinger

Answer 3

我已经使用递归生成器重写了这个组合函数。输出是一个迭代器。

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

- ovgolovin

Answer 4

代码行out.append(strng[i])与所描述的算法不符。您不想要追加，而是要将strng[i]设置为out[level]

- TJD

---

没错，但我把字符数组近似为一个简单的数组，可以在末尾连接。不过还是谢谢你提醒我！ - Rio