python - Compute all ways to bin a series of integers into N bins, where each bin only contains contiguous numbers -

i want find possible ways map series of (contiguous) integers m = {0,1,2,...,m} series of integers n = {0,1,2,...,n} m > n, subject constraint contiguous integers in m map same integer in n.

the following piece of python code comes close (start corresponds first element in m, stop-1 corresponds last element in m, , nbins corresponds |n|):

import itertools def find_bins(start, stop, nbins):     if (nbins > 1):         return list(list(itertools.product([range(start, ii)], find_bins(ii, stop, nbins-1))) ii in range(start+1, stop-nbins+2))     else:         return [range(start, stop)] 

e.g

in [20]: find_bins(start=0, stop=5, nbins=3) out[20]:  [[([0], [([1], [2, 3, 4])]), ([0], [([1, 2], [3, 4])]), ([0], [([1, 2, 3], [4])])], [([0, 1], [([2], [3, 4])]),  ([0, 1], [([2, 3], [4])])], [([0, 1, 2], [([3], [4])])]] 

however, can see output nested, , life of me, cant find way amend code without breaking it.

the desired output this:

in [20]: find_bins(start=0, stop=5, nbins=3) out[20]:  [[(0), (1), (2, 3, 4)], [(0), (1, 2), (3, 4)], [(0), (1, 2, 3), (4)], [(0, 1), (2), (3, 4)],  [(0, 1), (2, 3), (4)], [(0, 1, 2), (3), (4)]] 

i suggest different approach: partitioning n non-empty bins uniquely determined n-1 distinct indices marking boundaries between bins, first marker after first element, , final marker before last element. itertools.combinations() can used directly generate such index tuples, , it's matter of using them slice indices. so:

def find_nbins(start, stop, nbins):     itertools import combinations     base = range(start, stop)     nbase = len(base)     ixs in combinations(range(1, stop - start), nbins - 1):         yield [tuple(base[lo: hi])                lo, hi in zip((0,) + ixs, ixs + (nbase,))] 

then, e.g.,

for x in find_nbins(0, 5, 3):     print(x) 

displays:

[(0,), (1,), (2, 3, 4)] [(0,), (1, 2), (3, 4)] [(0,), (1, 2, 3), (4,)] [(0, 1), (2,), (3, 4)] [(0, 1), (2, 3), (4,)] [(0, 1, 2), (3,), (4,)] 

edit: making 2 problems

just noting there's more general underlying problem here: generating ways break arbitrary sequence n non-empty bins. specific question here applying sequence range(start, stop). believe viewing way makes code easier understand, here is:

def gbins(seq, nbins):     itertools import combinations     base = tuple(seq)     nbase = len(base)     ixs in combinations(range(1, nbase), nbins - 1):         yield [base[lo: hi]                lo, hi in zip((0,) + ixs, ixs + (nbase,))]  def find_nbins(start, stop, nbins):     return gbins(range(start, stop), nbins)