All possible subdivisions of a list

Question

I've just written a small recursive programme to generate all the possible subdivisions of a list:

def subdivisions(ls):
    yield [ls]
    if len(ls) > 1:
        for i in range(1, len(ls)):
            for lhs in subdivisions(ls[:i]):
                yield lhs + [ls[i:]]

>>> for x in subdivisions('abcd'): print x
... 
['abcd']
['a', 'bcd']
['ab', 'cd']
['a', 'b', 'cd']
['abc', 'd']
['a', 'bc', 'd']
['ab', 'c', 'd']
['a', 'b', 'c', 'd']

I've brute forced this and it's taken me a long time to figure out. I'm wondering what this is called, as I'm sure there is a name for it.

In general I'm wondering how to learn this stuff from a mathematical point of view and whether there are good well known programming libraries that cover useful algorithms like this (I know of https://docs.python.org/3/library/itertools.html )

---

[Edit] the question that this is marked as duplicate of - get all possible partitions of a set - gets a different answer.

It is looking for { {{1,2,3},{}} , {{1},{2,3}} , {{1,2},{3}} , {{1,3},{2}}, {{1},{2},{3}}} while a correct answer for me (in it's terminology) would be { {{1,2,3}} , {{1},{2,3}} , {{1,2},{3}} , {{1},{2},{3}}}

Also, the point of asking the question was to figure out what the terminology of this is; I'm calling it 'subdivisions'; that answer is calling it 'partitions'. I'm looking for a good resource which enumerates all of these patterns, so that people don't go reinventing the wheel.

Answer 1

Let me give some mathematical interpretation of this problem.

Imagine: you have list abcd. If you put some separators in it - like a|bc|d - you'll divide it into sublists. All the possible separators are a|b|c|d (their count is N-1, where N is a size of list). Let's call them (separators) 1, 2, 3.

Then all the subdivisions of your list will be generated by all the combinations of set {1, 2, 3}. There will be 2**3 = 8 of them: each element can be in combination or not. (All these combinations are called powerset).

That can help you to list all the subdivisions without recursion: you just to iterate binary numbers from 0b000 to 0b111 inclusive (range(0, 2**(N-1))):

from itertools import zip_longest, chain

def yield_possible_splits(string):
    N = len(string)
    for i in range(2 ** (N-1)):
        spaces_bitmask = bin(i).replace('0b', '').rjust(N, '0')
        spaces = [' ' if bit == '1' else '' for bit in spaces_bitmask]
        yield ''.join(chain(*zip_longest(spaces, string, fillvalue='')))

Or equivalent variant using itertools.product instead of binary manipulations:

from itertools import zip_longest, chain, product

def yield_possible_splits(string):
    N = len(string)
    for spaces in product(['', ' '], repeat=N-1):
        yield ''.join(chain(*zip_longest(string, spaces, fillvalue='')))

Usage:

print(list(yield_possible_splits('abcd')))
# ['abcd', 'abc d', 'ab cd', 'ab c d', 'a bcd', 'a bc d', 'a b cd', 'a b c d']

Answer 2

Finding all partitions of a list is equivalent to finding all sets of indices at which to slice the list.

By example, given the list l = [1, 2, 3, 4], we can represent the partition [[1, 2], [3], [4]] by the list of indices [2, 3]. In particular, there is a one-to-one correspondence between such list of indices and partitions.

This means, given a list l we can find the powerset of range(1, len(l)) and find each corresponding partition.

Code

This solution uses the powerset function from itertools recipes. Using generators is more efficient than using recursion.

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def partitions(lst):
    for indices in powerset(range(1, len(lst))):
        partition = []
        i = 0
        for j in indices:
            partition.append(lst[i:j])
            i = j
        partition.append(lst[i:])

        yield partition

Example

print(*partitions([1, 2, 3]))
# [[1, 2, 3]] [[1], [2, 3]] [[1, 2], [3]] [[1], [2], [3]]