Algorithm to generate (not quite) spanning set in Python

Question

This follows on from this question:

Given this input: [1,2,3,4]

I'd like to generate this set of sets in python:

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

So unlike the previous question, the order of the list is retained.

Ideally the code would work for n items in the list

Thanks very much

EDIT 2: Could anyone advise me on how to do this if the original input is a string rather than a list (where each word in the string becomes an item in a list). Thanks!

EDIT: added [1] [2, 3, 4] Sorry for the mistake

What you're trying to do was something like the part 1 of the question [Python: show all possible groupings of a list](http://stackoverflow.com/q/9088321/1132524). — Rik Poggi, Feb 07 '12 at 22:46
It is somewhat like that. Although I'd hope to generalise to splitting the list into 'up to n' parts — user1195889, Feb 07 '12 at 23:39

Niklas B. · Accepted Answer · 2012-02-08T11:41:39.810

You might also enjoy a recursive solution:

def span(lst):
  yield [lst]
  for i in range(1, len(lst)):
    for x in span(lst[i:]):
      yield [lst[:i]] + x

Explanation

We exploit recursion here to break the problem down. The approach is the following:

For every list, the whole list is a valid spanning: [1,2,3,4] => [[1,2,3,4]].

For every list that is longer than size 1, we can use the first item as a group and then apply the same algorithm on the remaining list to get all the combined results:

[1,2,3] => 
  [[1]] + [[2], [3]]  # => [[1], [2], [3]]
  [[1]] + [[2,3]]     # => [[1], [2,3]]

For every list that is longer than size 2, we can just as well use the first two items as a group and then apply the same algorithm on the remaining list and combine the results:

[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]]     # => [[1,2], [3], [4,5]]
  [[1,2]] + [[3,4,5]]        # => [[1,2], [3,4,5]]

We can see that the possible combinations on the right side are indeed all possible groupings of the remainder of the list, [3,4,5].

For every list that is longer than ... etc. Thus, the final algorithm is the following:

yield the whole list (it is always a valid spanning, see above)
For every possible splitting of the list, yield the left-hand part of the list combined with all possible spannings of the right-hand part of the list.

yield is a special keyword in Python that make the function a generator, which means that it returns a iterable object that can be used to enumerate all results found. You can transform the result into a list using the list constructor function: list(span([1,2,3,4])).

Can I just take a couple of hours to work through them, then I will do so :) — user1195889, Feb 08 '12 at 00:37
Would you be able to explain a little how this works to a novice - just a couple of lines in prose? Don't worry though if you don't have time — user1195889, Feb 08 '12 at 11:30

score 2 · Answer 2 · edited May 23 '17 at 12:02

Adjusting one of the solution from Python: show all possible groupings of a list:

from itertools import combinations

def cut(lst, indexes):
    last = 0
    for i in indexes:
        yield lst[last:i]
        last = i
    yield lst[last:]

def generate(lst, n):
    for indexes in combinations(list(range(1,len(lst))), n - 1):
        yield list(cut(lst, indexes))

data = [1,2,3,4]

for i in range(1, len(data)+1):  # the only difference is here
    for g in generate(data, i):
        print(g)

"""
[[1, 2, 3, 4]]
[[1], [2, 3, 4]]
[[1, 2], [3, 4]]
[[1, 2, 3], [4]]
[[1], [2], [3, 4]]
[[1], [2, 3], [4]]
[[1, 2], [3], [4]]
[[1], [2], [3], [4]]
"""

score 1 · Answer 3 · answered Feb 07 '12 at 22:59

import itertools
a = [1, 2, 3, 4]
n = len(a)
for num_splits in range(n):
    for splits in itertools.combinations(range(1, n), num_splits):
        splices = zip([0] + list(splits), list(splits) + [n])
        print([a[i:j] for i, j in splices])

prints

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

Algorithm to generate (not quite) spanning set in Python

3 Answers3

Explanation

Linked