Hi, > Aus einer Gesamtmenge von n Elementen werden k Elemente gewählt. Der > Wert k kann dabei einen Wert (ganzzahlig natürlich ;-)) zwischen 1 und n > liegen. > > Ich bin nun auf der Suche nach einem Algorithmus, welcher mir alle > Kombinationsmöglichkeiten (ohne Wiederholung & ohne Beachtung der > Reihenfolge sind es (n über k) Möglichkeiten -> Binomialkoeffizient) > AUFLISTET. > > Hat da jemand von Euch eine Idee? oder sowas evtl. schonmal gemacht?
Ja, mehrere. Fast taeglich. Also nicht genau das, aber aehnliche Probleme. > oder einen Tipp, wo ich fündig werden könnte? Grundlagenliteratur der Informatik, Kapitel "Algorithmierung"... ;-) Du hast mindestens die Haelfte des Problems schon geloest indem Du ausgerechnet hast wieviele Moeglichkeiten es geben muss. Verschiedene Ansaetze draengen sich foermlich auf: der holistische Ansatz: erzeuge alle Kombinationen von n Elementen, kuerze jede davon auf k Elemente, sortiere, verwirf die Duplikate (Laufzeit steigt exponentiell mit n) der stochastische Ansatz: erwuerfle zufaellig Kombinationen von k Elementen, schaue ob Du diese Kombination schon kennst, hoere auf, wenn du k ueber n verschiedene hast (Laufzeit ist stochastisch und vermutlich sehr hoch - neuere Bitcoin-Miner haben aehnliche Probleme...) der systematische Ansatz: geh' rekursiv durch die k Stellen Deiner Kombinationen, fuer jede Rekursion: gehe durch alle Elemente, die Du noch verwenden kannst, haenge eines davon an die aktuelle Kombination an, fuer jedes davon gibt die Teil-Kombination an die naechste Rekursionsstufe, stoppe die Rekursion bei k (Laufzeit steigt exponentiell mit k, Speicherverbrauch linear mit k) Als Uebung fuer die hoeheren Semester kann man auch eine Rekursion in eine Iteration verwandeln oder umgekehrt oder man kann Speicher- und Laufzeit-verbrauch gegeneinander tauschen/optimieren Profi-Tipp: verweigere die Zusammenarbeit wenn k ueber n den Wertebereich von 32bit Integer ueberschreitet (siehe Laufzeit). Lass mal hoeren wie Du diese Ideen (oder andere) umsetzen wuerdest, wir helfen dann weiter, wenn Du stecken bleibst bzw. optimieren willst... Konrad _______________________________________________ Lug-dd maillist - [email protected] https://ssl.schlittermann.de/mailman/listinfo/lug-dd
