4

各ビンに少なくとも1つのアイテムが含まれるように、N個のアイテムのコレクションのすべてのパーティションをK個のビンに生成するアルゴリズム（またはストレートPythonコード）を提供します。順序が重要な場合と順序が重要でない場合の両方でこれが必要です。

順序が重要な例

>>> 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 に答える