4

给出一个算法（或直接的 Python 代码），将 N 个项目集合的所有分区生成 K 个 bin，使得每个 bin 至少有一个项目。在订单很重要和订单不重要的情况下，我都需要这个。

顺序很重要的示例

>>> 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 中提出了这个要求，但我也愿意翻译一个清晰的算法。

4

2 回答 2

4

您需要一个递归函数来解决此类问题：您获取列表，获取长度增加的子部分，并将相同的过程应用于 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]]
于 2012-10-30T02:40:29.430 回答
3

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
        #  http://stackoverflow.com/questions/13131491/
        #  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
于 2012-11-01T19:18:09.230 回答