- A+

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.

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