Yield sub combinations with constraint on lenght of output list

Question

This question is probably a combination of following two questions, but with slightly different perspective.

I adapted the code in first question for my requirement.

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)

This gives output as:

[[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]]

Now the problem is, this takes too much time for larger sized lists. Is there more efficient/pythonic way of implementing this? How could I incorporate argument 'max' in the function itself? I tried a lot of ways, but having hard time working with recursive functions.

score 4 · Accepted Answer · answered Jul 02 '12 at 12:01

It seems your desired result can be described as all the ways to split a list in (say) 4 non-empty sublists. This can be done by generating all possible combinations of split positions:

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)]

Example output:

>>> 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]]]

Yield sub combinations with constraint on lenght of output list

1 Answers1