Verknüpfung von Funktionen

[hcshm]

Ich doktere seit Tagen an der Verknüpfung von Funktionen herum. Es geht in meinem Beispiel um k-elementige Mengen von Zahlen aus einer Menge L. Die beiden hierfür im Lehrbuch aufgeführten Module (Kombinationsgenerierung und Filterung auf Doppelungen) habe ich nachvollziehen könnten (Weitz, Konkrete Mathematik, 2.Aufl., S. 247). Allerdings gelingt es mir nicht, die beiden Module zu verknüpfen, so dass ich mit einem einzigen Befehl ein Ergebnis erhalte (keine Hinweise im Buch hierzu). Kann mir bitte jemand helfen?

def combs(L, k):
if k == 0:
yield frozenset()
else:
done = set()
for x in L:
done.add(x)
for P in combs(L-done, k-1):
yield frozenset([x]) | P


def fixed_size_subsets(n):
k = n
seen = set()
while True:
for s in combs(set(range(k)), n):
if not s in seen:
yield s
seen.add(s)
k += 1

[grubenfox]

... und wo ist das zweite Modul? Die beiden aufgeführten Funktionen sind ja miteinander verknüpft.

[__deets__]

Bitte Code-Tags benutzen, damit die in Python wichtigen Einrueckungen erhalten bleiben. Und vollstaendigen Code mit der Fehlermeldung und/oder Erwartungshaltung. Ich sehe zB keinen Aufruf deiner Funktionen. Dann kann ja auch nichts passieren.

[Sirius3]

Ich frage mich, was die Funktion mit Kämmen zu tun hat?
Wenn Du combinations meinst, solltest Du die Funktion auch so benennen.
Variablennamen werden generell klein geschrieben. L ist auch ein komischer Name, für was eigentlich?

Statt `not s in seen` benutzt man `s not in seen`. Für einen unendlichen Zähler benutzt man itertools.count:

Code: Alles auswählen

def fixed_size_subsets(n):
    seen = set()
    for k in itertools.count(n):
        for s in combs(set(range(k)), n):
            if s not in seen:
                yield s
                seen.add(s)

Nun ist es aber unsinnig, ständig Kombinationen zu erzeugen, die man schon gesehen hat, besser wäre es, einen Algorithmus zu benutzen, wo das gar nicht nötig ist:

Code: Alles auswählen

def fixed_size_subsets(n):
    for k in itertools.count(n - 1):
        for s in combs(set(range(k)), n - 1):
            yield s | {k}

Was Dein eigentliches Problem ist, habe ich aber noch nicht verstanden.

[hcshm]

Vielen Dank für die wertvolle Hilfe bis hierhin. Das nächste Mal werde ich natürlich versuchen, den - jetzt aus dem Lehrbuch übernommenen - Code in angemessene Python-Nomenklatur zur bringen.
L oben bezeichnet eine Menge von Elementen, z.B. {1, 2, 3, 4}, combs (combinations) eine Kombination dieser Elemente, bei k = 2 also z.B. {1, 2}.

Mir geht es um den Aufruf der beiden verknüpften Funktionen in einem Befehl.

[Sirius3]

Die Funktion `fixed_size_subsets` ist eine nette Spielerei, aber eine sinnvolle Verwendung fällt mir hier nicht ein. Was für ein Problem willst Du denn mit der Funktio lösen?

Bei endlos laufenden Generatoren ist eine Abbruchbedingung nötig, ansonsten kann man sie in einer for-Schleife benutzen, wie jedes andere iterierbare Objekt:

Code: Alles auswählen

for combination in fixed_size_subsets(4):
    if some_condition(combination):
        break
    do_something(n)

[hcshm]

Die Fragestellung ist:
- Suche aus einer n-elementigen Menge die k-elementigen Kombinationen - und mache das bitte rekursiv (erste Funktion oben)
- Im zweiten Schritt eliminiere die doppelten (zweite Funktion oben, die Du optimiert hast). (Bei n = 4 und k = 2 wird die Kombination {1, 2} natürlich sowohl aus {1, 2, 3} als auch aus {1, 2, 3, 4 } extrahiert.

Ich möchte die beiden verknüpften Funktionen mit einem Befehl aufrufen.

Der Autor des Buches schreibt übrigens: "Das ist natürlich überhaupt nicht effizient und jeder angewandte Informatiker wird aufschreien, wenn er diesen Code sieht. Aber hier geht es ja um theoretische Überlegungen." Insofern bin ich besonders dankbar, dass ich hoffentlich nicht nur Hilfe bei meiner Frage - Aufruf mit einem Befehl - erhalte, sondern dass Du Dir dir Mühe gemacht hast, den Code in "ordentliches Python" zu bringen. Bereits jetzt vielen Dank!

[__deets__]

Dann musst du eine dritte Funktion schreiben. Oder einen Ausdruck, der die eine als argument der anderen aufruft.

[hcshm]

Vielen Dank für die wertvolle Unterstützung! Die Aufgabe ist wie nachfolgend jetzt gelöst.

Code: Alles auswählen

"""Umsetzung / Anpassung des Codes aus einem Lehrbuch:
Generierung von Kombinationen (Funktion 1) und Filterung
auf Doppel (Funktion 2) """

def combinations(elements, subset_length):
    if subset_length == 0:
        yield frozenset()
    else:
        done = set()
        for x in elements:
            done.add(x)
            for P in combinations(elements - done, subset_length - 1):
                yield frozenset([x]) | P


def fixed_size_subsets(subset_length, limit):
    start_n =  subset_length
    seen = set()
    while True:
        if start_n > limit:
            break
        for s in combinations(set(range(start_n)), subset_length):
            if s not in seen:
                yield s
                seen.add(s)
        start_n += 1


fs_subsets_beisp = fixed_size_subsets(2, 5)
print(list(fs_subsets_beisp))

[__blackjack__]

@hcshm: Die ``while``-Schleife ist ja ziemlich offensichtlich eine ``for``-Schleife. Womit die Funktion vier Zeilen kürzer wird.

[grubenfox]

Vier? sind es nicht drei? Die letzten beiden Zeilen könnte man auch noch zusammenfassen...

print(list(fixed_size_subsets(2, 5)))

[__blackjack__]

Erste Zuweisung an `start_n` (1), das ``if … break`` (2), und das Hochzählen von `start_n` am Ende der Schleife (1) macht zusammen 4 Zeilen. Und das ist ein guter Grund es zu tun, wenn man selbst bei so kurzem Code schon was übersehen kann, weil das über die ganze Funktion verteilt ist, was eigentlich ein *einer* ``for …``-Zeile stehen sollte.

[Sirius3]

Wenn man ein fixes Limit hat, braucht man gar keine Schleife:

Code: Alles auswählen

def fixed_size_subsets(subset_length, limit): 
    yield from combinations(set(range(limit)), subset_length)