Herstellung aller Gruppen von Kombinationen fester Länge

Question

Ich suche nach einem Algorithmus und/oder Python-Code, um alle möglichen Arten der Partitionierung einer Menge von n Elementen in null oder mehr Gruppen von r Elementen und einem Rest zu generieren. Zum Beispiel, gegeben eine Menge:

[1,2,3,4,5]

mit n = 5 und r = 2, möchte ich folgendes erhalten:

((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,))
...

Mit anderen Worten, das Ergebnis besteht aus der Extraktion von 0 Gruppen von zwei Elementen aus der Menge, plus den Ergebnissen der Extraktion von 1 Gruppe von zwei Elementen aus der Menge, plus den Ergebnissen der Extraktion von 2 Gruppen von zwei Elementen aus der Menge,... wenn n größer wäre, würde dies fortgesetzt werden.

Die Reihenfolge, in der diese Ergebnisse generiert werden, ist nicht wichtig, ebenso wenig wie die Reihenfolge der Elemente innerhalb jeder einzelnen Gruppe oder die Reihenfolge der Gruppen innerhalb eines Ergebnisses. (z.B. ((1,3),(2,4,5)) ist äquivalent zu ((3,1),(4,5,2)) und zu ((2,5,4),(1,3)) und so weiter.) Was ich suche, ist, dass jedes unterschiedliche Ergebnis mindestens einmal produziert wird, und vorzugsweise genau einmal, auf effizienteste Weise.

---

Die Methode des Brute-Force besteht darin, alle möglichen Kombinationen von r aus den n Elementen zu generieren, dann alle möglichen Gruppen von einer beliebigen Anzahl dieser Kombinationen zu erstellen (die Potenzmenge), über sie zu iterieren und nur die zu verarbeiten, bei denen die Kombinationen in der Gruppe keine Elemente gemeinsam haben. Das dauert viel zu lange, selbst für eine kleine Anzahl von Elementen (es erfordert die Iteration über 2^(n!/r!(n-r)!) Gruppen, daher ist die Komplexität doppel-exponentiell).

Basierend auf dem in dieser Frage gegebenen Code, der im Wesentlichen der spezielle Fall für r = 2 und gerade n ist, habe ich folgendes entwickelt:

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)

Was tatsächlich alle möglichen Ergebnisse zu generieren scheint, aber einige Duplikate enthält, eine nicht unerhebliche Anzahl davon, wenn n recht groß ist. Daher hoffe ich auf einen Algorithmus, der die Duplikate vermeidet.

Answer 1

Wie wäre es damit?

from itertools import combinations

def partitions(s, r):
    """
    Generiert Partitionen des Iterators `s` in Teilmengen der Größe `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):
    """
    Generiert Partitionen des Iterators `s` in Teilmengen der Größe
    `r` plus einem Rest.

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

Das Beispiel vom 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,))]