在Python中遍历分区

Question

我在想，在Python中，如何以最好的方式遍历一个给定大小的列表分区。

比如说，我们有一个列表 [1,2,3,4,5]，我们想要 k=3 个分区。一个比较糟糕的方法是这样写：

lst = [1,2,3,4,5]
for i in range(1,len(lst)):
    for j in range(i+1, len(lst)):
        print lst[:i], lst[i:j], lst[j:]

这样做的结果是

[1], [2], [3,4,5]
[1], [2,3], [4,5]
...
[1,2,3], [4], [5]

但是如果我后来想要遍历 k=4 个分区，那我就得在循环里再加一层，这在运行时是做不到的。理想情况下，我想写成这样：

for part in partitions([1,2,3,4,5], k):
    print part

有没有人知道最好的方法是什么？

Answer 1

对于较大的列表，这种方法可能效率不高，但它是可行的：

from itertools import product, islice

def partitions(seq, k):
    for c in product(xrange(1, len(seq)+1), repeat=k):
        if sum(c) == len(seq):
            it = iter(seq)
            yield [list(islice(it, x)) for x in c]

for part in partitions([1,2,3,4,5], 3):
    print part

输出结果：

[[1], [2], [3, 4, 5]]
[[1], [2, 3], [4, 5]]
[[1], [2, 3, 4], [5]]
[[1, 2], [3], [4, 5]]
[[1, 2], [3, 4], [5]]
[[1, 2, 3], [4], [5]]

对于更大的列表，你需要找到所有大小为 k 的子集，这些子集来自于 range(1, len(sequence)+1)，并且它们的总和要等于序列的长度，然后根据这些子集来切割序列。

相关链接： http://www.algorithmist.com/index.php/Coin_Change

Answer 2

我通过写下面的代码实现了我想要的效果：

from itertools import tee, izip, combinations

def partitions(items, k):
    N = len(items)

    def pairwise(iterable):  # Taken from itertools recipies
        a, b = tee(iterable)
        next(b, None)
        return izip(a, b)

    def applyPart(part, items):
        lists = []
        for l,h in pairwise([0] + part + [N]):
            lists.append(items[l:h])
        return lists

    for part in combinations(range(1, N), k - 1):
        yield applyPart(list(part), items)

Answer 3

我会用和你一样的想法，只是不使用 pairwise 这个东西：

from itertools import combinations

def partitions(items, k):

    def split(indices):
        i=0
        for j in indices:
            yield items[i:j]
            i = j
        yield items[i:]

    for indices in combinations(range(1, len(items)), k-1):
        yield list(split(indices))