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 )


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

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: