2

这个问题可能是以下两个问题的组合,但角度略有不同。

产生子组合

有限制的收益子组合

我根据我的要求调整了第一个问题中的代码。

def sub_combinations(segment):
    for i in range(1, len(segment)):
            for j in sub_combinations(segment[i:]):
                    yield [segment[:i]] + j 
    yield [segment]

max = 4

for p in sub_combinations([1, 2, 3, 4, 5, 6, 7]):
    if len(p) == max:
        print map(list, p)

这给出了输出:

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

现在的问题是,对于较大的列表来说,这需要太多时间。有没有更有效/pythonic的方式来实现这个?我怎样才能在函数本身中加入参数“max”?我尝试了很多方法,但很难使用递归函数。

4

1 回答 1

4

似乎您想要的结果可以描述为将列表拆分为(例如)4 个非空子列表的所有方法。这可以通过生成所有可能的拆分位置组合来完成:

def split_sequence(seq, chunks):
    for splits in itertools.combinations(range(1, len(seq)), chunks - 1):
        left = (None,) + splits
        right = splits + (None,)
        yield [seq[l:r] for l, r in zip(left, right)]

示例输出:

>>> list(split_sequence(range(7), 4))
[[[0], [1], [2], [3, 4, 5, 6]],
 [[0], [1], [2, 3], [4, 5, 6]],
 [[0], [1], [2, 3, 4], [5, 6]],
 [[0], [1], [2, 3, 4, 5], [6]],
 [[0], [1, 2], [3], [4, 5, 6]],
 [[0], [1, 2], [3, 4], [5, 6]],
 [[0], [1, 2], [3, 4, 5], [6]],
 [[0], [1, 2, 3], [4], [5, 6]],
 [[0], [1, 2, 3], [4, 5], [6]],
 [[0], [1, 2, 3, 4], [5], [6]],
 [[0, 1], [2], [3], [4, 5, 6]],
 [[0, 1], [2], [3, 4], [5, 6]],
 [[0, 1], [2], [3, 4, 5], [6]],
 [[0, 1], [2, 3], [4], [5, 6]],
 [[0, 1], [2, 3], [4, 5], [6]],
 [[0, 1], [2, 3, 4], [5], [6]],
 [[0, 1, 2], [3], [4], [5, 6]],
 [[0, 1, 2], [3], [4, 5], [6]],
 [[0, 1, 2], [3, 4], [5], [6]],
 [[0, 1, 2, 3], [4], [5], [6]]]
于 2012-07-02T12:01:29.873 回答