在Python中将N个项目分成K个容器的惰性分区

Question

给出一个算法（或直接使用Python代码），将N个物品分成K个容器的所有可能组合列举出来，其中每个容器至少包含一个物品。我需要两种情况：一种是考虑顺序，另一种是不考虑顺序。

例子（考虑顺序）：

>>> list(partition_n_in_k_bins_ordered((1,2,3,4), 2))
[([1], [2,3,4]), ([1,2], [3,4]), ([1,2,3], [4])]

>>> list(partition_n_in_k_bins_ordered((1,2,3,4), 3))
[([1], [2], [3,4]), ([1], [2,3], [4]), ([1,2], [3], [4])]

>>> list(partition_n_in_k_bins_ordered((1,2,3,4), 4))
[([1], [2], [3], [4])]

不需要考虑顺序的示例

>>> list(partition_n_in_k_bins_unordered({1,2,3,4}, 2))
[{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}}, {{4}, {1,2,3}},
 {{1,2}, {3,4}}, {{1,3}, {2,4}}, {{1,4}, {2,3}}]

这些函数应该生成惰性迭代器/生成器，而不是列表。最好使用 itertools 中找到的原语。我怀疑有一种聪明的解决方案正逃脱着我的注意力。

虽然我在 Python 中提出了这个问题，但我也愿意翻译一个清晰的算法。

- MRocklin

---

“where order matters” 是什么意思？在那种情况下，您似乎将项目视为不可区分的。 - Ronan Lamy

好问题。“顺序很重要”可能有几种含义，如果分区被展平，则项目应与输入相同（请注意[[1]，[2]，[3,4]]按顺序[1,2,3,4]排序）。这些项目是可区分的。因此，例如解决方案[[2]，[1]，[3,4]]将无效。 - MRocklin

在这种情况下，您可以将问题分解为查找项目数量，然后为两种情况生成列表。 - Ronan Lamy

在有序的情况下，您要寻找整数组合，而在无序的情况下，要寻找整数分割。我不确定两者的最佳算法是什么，但它们都是经典问题。 - Ronan Lamy

如果您允许空箱，对于您的应用程序而言，它们将代表身份。 - asmeurer

谢谢您提供的链接，@RonanLamy。我正在查看它们。 - MRocklin

Answer 1

你需要一个递归函数来解决这种问题：你需要取出列表的一部分，长度逐渐增加，并将同样的过程应用到剩余列表的n-1个部分中。

这是我对有序组合的理解。

def partition(lista,bins):
    if len(lista)==1 or bins==1:
        yield [lista]
    elif len(lista)>1 and bins>1:
        for i in range(1,len(lista)):
            for part in partition(lista[i:],bins-1):
                if len([lista[:i]]+part)==bins:
                    yield [lista[:i]]+part

for i in partition(range(1,5),1): 
    print i
#[[1, 2, 3, 4]]

for i in partition(range(1,5),2): 
    print i
#[[1], [2, 3, 4]]
#[[1, 2], [3, 4]]
#[[1, 2, 3], [4]]

for i in partition(range(1,5),3):
    print i
#[[1], [2], [3, 4]]
#[[1], [2, 3], [4]]
#[[1, 2], [3], [4]] 

for i in partition(range(1,5),4):
    print i
#[[1], [2], [3], [4]]

- EnricoGiampieri

---

这不包括分区[[1, 3]，[2, 4]]。 - asmeurer

啊，那你只是解决了第一部分。 - asmeurer

类似/相关 - mbomb007

Answer 2

Enrico算法、Knuth算法和我的粘合剂都可以用来拼接一些东西，返回列表或集合的列表（如果元素不可哈希，则返回为列表的列表）。

def kbin(l, k, ordered=True):
    """
    Return sequence ``l`` partitioned into ``k`` bins.

    Examples
    ========

    The default is to give the items in the same order, but grouped
    into k partitions:

    >>> for p in kbin(range(5), 2):
    ...     print p
    ...
    [[0], [1, 2, 3, 4]]
    [[0, 1], [2, 3, 4]]
    [[0, 1, 2], [3, 4]]
    [[0, 1, 2, 3], [4]]

    Setting ``ordered`` to None means that the order of the elements in
    the bins is irrelevant and the order of the bins is irrelevant. Though
    they are returned in a canonical order as lists of lists, all lists
    can be thought of as sets.

    >>> for p in kbin(range(3), 2, ordered=None):
    ...     print p
    ...
    [[0, 1], [2]]
    [[0], [1, 2]]
    [[0, 2], [1]]

    """
    from sympy.utilities.iterables import (
        permutations, multiset_partitions, partitions)

    def partition(lista, bins):
        #  EnricoGiampieri's partition generator from
        #  https://dev59.com/HWrWa4cB1Zd3GeqP8TeX
        #  partition-n-items-into-k-bins-in-python-lazily
        if len(lista) == 1 or bins == 1:
            yield [lista]
        elif len(lista) > 1 and bins > 1:
            for i in range(1, len(lista)):
                for part in partition(lista[i:], bins - 1):
                    if len([lista[:i]] + part) == bins:
                        yield [lista[:i]] + part
    if ordered:
        for p in partition(l, k):
            yield p
    else:
        for p in multiset_partitions(l, k):
            yield p

- Chris Smith