Compute all ways to bin a series of integers into N bins, where each bin only contains contiguous numbers
<p>I want find all possible ways to map a series of (contiguous) integers M = {0,1,2,...,m} to another series of integers N = {0,1,2,...,n} where m > n, <em>subject to the constraint that only contiguous integers in M map to the same integer in N.</em> </p>

<p>The following piece of python code comes close (<code>start</code> corresponds to the first element in M, <code>stop</code>-1 corresponds to the last element in M, and <code>nbins</code> corresponds to |N|):</p>

<pre><code>import itertools
def find_bins(start, stop, nbins):
    if (nbins &gt; 1):
        return list(list(itertools.product([range(start, ii)], find_bins(ii, stop, nbins-1))) for ii in range(start+1, stop-nbins+2))
    else:
        return [range(start, stop)]
</code></pre>

<p>E.g </p>

<pre><code>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])])]]
</code></pre>

<p>However, as you can see the output is nested, and for the life of me, I cant find a way to properly amend the code without breaking it.</p>

<p>The desired output would look like this:</p>

<pre><code>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)]]
</code></pre>

<p>This does what I want; I will gladly accept simpler, more elegant solutions:</p>

<pre><code>def _split(start, stop, nbins):
    if (nbins &gt; 1):
        out = []
        for ii in range(start+1, stop-nbins+2):
            iterator = itertools.product([range(start, ii)], _split(ii, stop, nbins-1))
            for item in iterator:
                out.append(item)
        return out
    else:
        return [range(start, stop)]

def _unpack(nested):
    unpacked = []
    if isinstance(nested, (list, tuple)):
        for item in nested:

            if isinstance(item, tuple):
                for subitem in item:
                    unpacked.extend(_unpack(subitem))

            elif isinstance(item, list):
                unpacked.append([_unpack(subitem) for subitem in item])

            elif isinstance(item, int):
                unpacked.append([item])

        return unpacked

    else: # integer
        return nested

def find_nbins(start, stop, nbins):
    nested = _split(start, stop, nbins)
    unpacked = [_unpack(item) for item in nested]
    return unpacked
</code></pre>

python combinatorics