5

n一連の要素を 0 個以上のr要素グループと残りの要素に分割するすべての可能な方法を生成するアルゴリズムおよび/または Python コードを探しています。たとえば、次のセットがあるとします。

[1,2,3,4,5]

とn = 5でr = 2、取得したい

((1,2,3,4,5),)
((1,2),(3,4,5))
((1,3),(2,4,5))
...
((1,2),(3,4),(5,))
((1,2),(3,5),(4,))
...

つまり、セットから 2 つのアイテムのグループを 0 個抽出した結果、セットから 2 つのアイテムのグループを 1 つ抽出した結果、およびセットから 2 つのアイテムのグループを 2 つ抽出した結果、...nが大きい場合、これは続くでしょう。

これらの結果が生成される順序は重要ではなく、個々のグループ内の要素の順序も、結果内のグループの順序も重要ではありません。(例:とと などと((1,3),(2,4,5))同等です。) 私が求めているのは、すべての個別の結果が、可能な限り効率的な方法で少なくとも 1 回、できれば正確に 1 回生成されることです。((3,1),(4,5,2))((2,5,4),(1,3))

力ずくの方法はr、n要素から可能なすべての組み合わせを生成し、それらの組み合わせの任意の数 ( powerset ) のすべての可能なグループを作成し、それらを反復処理して、グループ内の組み合わせに要素がないもののみを処理することです。一般。少数の要素でも時間がかかりすぎます (2^(n!/r!(nr)!) グループを反復処理する必要があるため、複雑さは二重指数関数的です)。

この質問で指定されたコードに基づいて、これは本質的にr = 2andの特殊なケースでありn、次のように思いつきました。

def distinct_combination_groups(iterable, r):
    tpl = tuple(iterable)
    yield (tpl,)
    if len(tpl) > r:
        for c in combinations(tpl, r):
            for g in distinct_combination_groups(set(tpl) - set(c), r):
                yield ((c,) + g)

これは考えられるすべての結果を生成するように見えますが、いくつかの重複が含まれていますn。したがって、重複を回避するアルゴリズムを期待しています。

4

1 に答える 1

9

これはどう？

from itertools import combinations

def partitions(s, r):
    """
    Generate partitions of the iterable `s` into subsets of size `r`.

    >>> list(partitions(set(range(4)), 2))
    [((0, 1), (2, 3)), ((0, 2), (1, 3)), ((0, 3), (1, 2))]
    """
    s = set(s)
    assert(len(s) % r == 0)
    if len(s) == 0:
        yield ()
        return
    first = next(iter(s))
    rest = s.difference((first,))
    for c in combinations(rest, r - 1):
        first_subset = (first,) + c
        for p in partitions(rest.difference(c), r):
            yield (first_subset,) + p

def partitions_with_remainder(s, r):
    """
    Generate partitions of the iterable `s` into subsets of size
    `r` plus a remainder.

    >>> list(partitions_with_remainder(range(4), 2))
    [((0, 1, 2, 3),), ((0, 1), (2, 3)), ((0, 2), (1, 3)), ((0, 3), (1, 2))]
    >>> list(partitions_with_remainder(range(3), 2))
    [((0, 1, 2),), ((1, 2), (0,)), ((0, 2), (1,)), ((0, 1), (2,))]
    """
    s = set(s)
    for n in xrange(len(s), -1, -r): # n is size of remainder.
        if n == 0:
            for p in partitions(s, r):
                yield p
        elif n != r:
            for remainder in combinations(s, n):
                for p in partitions(s.difference(remainder), r):
                    yield p + (remainder,)

OPの例：

>>> pprint(list(partitions_with_remainder(range(1, 6), 2)))
[((1, 2, 3, 4, 5),),
 ((4, 5), (1, 2, 3)),
 ((3, 5), (1, 2, 4)),
 ((3, 4), (1, 2, 5)),
 ((2, 5), (1, 3, 4)),
 ((2, 4), (1, 3, 5)),
 ((2, 3), (1, 4, 5)),
 ((1, 5), (2, 3, 4)),
 ((1, 4), (2, 3, 5)),
 ((1, 3), (2, 4, 5)),
 ((1, 2), (3, 4, 5)),
 ((2, 3), (4, 5), (1,)),
 ((2, 4), (3, 5), (1,)),
 ((2, 5), (3, 4), (1,)),
 ((1, 3), (4, 5), (2,)),
 ((1, 4), (3, 5), (2,)),
 ((1, 5), (3, 4), (2,)),
 ((1, 2), (4, 5), (3,)),
 ((1, 4), (2, 5), (3,)),
 ((1, 5), (2, 4), (3,)),
 ((1, 2), (3, 5), (4,)),
 ((1, 3), (2, 5), (4,)),
 ((1, 5), (2, 3), (4,)),
 ((1, 2), (3, 4), (5,)),
 ((1, 3), (2, 4), (5,)),
 ((1, 4), (2, 3), (5,))]
于 2013-01-28T17:02:36.483 に答える