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>I suggest a different approach:  a partitioning into <code>n</code> non-empty bins is uniquely determined by the <code>n-1</code> distinct indices marking the boundaries between the bins, where the first marker is after the first element, and the final marker before the last element.  <code>itertools.combinations()</code> can be used directly to generate all such index tuples, and then it's just a matter of using them as slice indices.  Like so:</p>

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

<p>Then, e.g.,</p>

<pre><code>for x in find_nbins(0, 5, 3):
    print(x)
</code></pre>

<p>displays:</p>

<pre><code>[(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>

<h2>EDIT:  Making it into 2 problems</h2>

<p>Just noting that there's a more general underlying problem here:  generating the ways to break an arbitrary sequence into <code>n</code> non-empty bins.  Then the specific question here is applying that to the sequence <code>range(start, stop)</code>.  I believe viewing it that way makes the code easier to understand, so here it is:</p>

<pre><code>def gbins(seq, nbins):
    from itertools import combinations
    base = tuple(seq)
    nbase = len(base)
    for ixs in combinations(range(1, nbase), nbins - 1):
        yield [base[lo: hi]
               for lo, hi in zip((0,) + ixs, ixs + (nbase,))]

def find_nbins(start, stop, nbins):
    return gbins(range(start, stop), nbins)
</code></pre>

python combinatorics