计算将一系列整数分箱到 N 个箱中的所有方法，其中每个箱只包含连续的数字

Question

我想找到所有可能的方法将一系列（连续的）整数 M = {0,1,2,...,m} 映射到另一系列整数 N = {0,1,2,. ..,n} 其中 m > n，受限于 M 中只有连续的整数映射到 N 中的相同整数的约束。

下面这段python代码接近（start对应M中的第一个元素，stop-1对应M中的最后一个元素，nbins对应|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))) for ii in range(start+1, stop-nbins+2))
    else:
        return [range(start, stop)]

例如

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])])]]

但是，如您所见，输出是嵌套的，对于我来说，我无法找到一种方法来正确修改代码而不破坏它。

所需的输出如下所示：

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)]]

Answer 1

这就是我想要的；我很乐意接受更简单、更优雅的解决方案：

def _split(start, stop, nbins):
    if (nbins > 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

Answer 2

我建议采用不同的方法：划分为 n 个非空箱由标记箱之间边界的 n-1 个不同索引唯一确定，其中第一个标记在第一个标记之后元素，以及最后一个元素之前的最终标记。 itertools.combinations() 可以直接使用生成所有这样的索引元组，然后将它们用作切片索引就可以了。像这样：

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,))]

然后，例如，

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

显示：

[(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,)]

编辑：将其变成 2 个问题

只是注意到这里有一个更普遍的潜在问题：生成将任意序列分解为 n 非空箱的方法。那么这里的具体问题是将其应用于序列 range(start, stop)。我相信以这种方式查看它会使代码更容易理解，所以这里是：

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)

计算将一系列整数分箱到 N 个箱中的所有方法，其中每个箱只包含连续的数字

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

python

combinatorics

编辑：将其变成 2 个问题