# All possible subdivisions of a list

• A+
Category：Languages

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 )

 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.

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