Hallo Konrad,
vielen Dank für deine ausführliche Antwort und die unterschiedlichen Lösungsansätze.
In der Mittagspause kam mir noch eine andere Idee zur Lösung dieses Problemes. Und zwar folgende:
1. Man nehme einen Vektor, der alle n Elemente enthält. 2. Man berechne alle möglichen Kombinationen C für k aus n Elementen (für k=1 bis k=n). Es ergeben sich aus der Summe der Binomialkoeffizienten 2^n-1 Möglichkeiten. 3. Iteration von 1 bis C in der... 4. der Schleifenzähler in eine n-Bit Binärzahl (Vektor mit n-Elementen) umgewandelt wird 5. und die Binärcodierung mit dem Vektor, der die Elemente enthält, multipliziert wird. Dadurch bleiben in dem Vektor die ausgewählten (in der Kombination enthaltenen) Elemente erhalten und der Rest wird 0)
Optional: Wenn man nur die Kombinationen für einen Wert k ausgeben möchte, bietet sich an die Summe über den Binärzahlvektor zu bilden und damit nur die Kombinationen auszugeben, deren "Binärsumme" dem Wert k entspricht.
Wenn man die Kombinationen für alle Werte k benötigt treten mit diesem Ansatz weder unnötige Berechnungen, noch Dopplungen von Kombinationen auf und es sind auch keine rekursiven Aufrufe notwendig =) Der Nachteil ist, dass man 0 nicht als Element verwenden kann ;-)
Doreen
Am 24.04.2014 14:20, schrieb konrad@silmor.de:
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 - Lug-dd@mailman.schlittermann.de https://ssl.schlittermann.de/mailman/listinfo/lug-dd