 |
 |
 |
 |
 |
 |
Startseite » Forum » Kombinationen
Kombinationen
Universität / Fachhochschule
Tags: Ich suche die Anzahl von Kombinationen von 13 aus 9 Elementen
 
|
  |
|---|
|
Also ganz konkret: sagen wir es gibt die Elemente A ... I nun schaue ich mir einen konkreten Fall an, z.B.: A A A A B B C C D D E F G Meine Frage ist zweigeteilt: 1. wieviele unterschiedliche Kombinationen (ohne Wiederholung) gibt es dafür? Ich würde so vorgehen: Betrachte ich alle (im konkreten Fall 13) Elemente als unterschiedlich so gibt es 13! Permutationen. Davon sind aber im konkreten fall immer 4!*2!*2!*2! gleich, richtig? es gäbe also (13!)/(4!*2!*2!*2!) unterschiedliche Kombinationen? Allgemeiner also: Bei einer Länge von m aus n Elementen mit m>n und l1...limax Wiederholungen ist die Anzahl der Kombinationen ohhne Wiederholungen wobei m-(l1-1)-...-(lmax-1)=n (im obigen Beispiel: 13 - 3 - 1 - 1 - 1 = 7 = Zahl der verwendeten Elemente A...G) Stimmt Ihr mir da zu? 2. ich suche nun nach einem möglichst schlauen Algorythmus, diese zu finden. Natürlich kann ich einen Rechner ansetzen und die (in diesem Fall) 88 Milliarden Permutationen durchrechnen lassen und hinterher die doppelten rausschmeißen. das scheint mir aber recht aufwändig. Hat jemand einen schlaueren Algoprythmus? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, Deine Überlegung für das Beispiel ist richtig. Allerdings verstehe ich die allgemeine Formel noch nicht. Was ist der Unterschied zwischen und imax? Was einen Algorithmus angeht: Man kann die Kombinationen in "lexikografischer Ordnung" auflisten lassen. Man behandelt die Kombinationen wie ein Wort und verwendet die Anordnung wie in einem Lexikon. Man kann dann programmieren, wie sich zu einem Wort das nächst höhere (mit den gegebenen Einschränkungen) finden lässt. Dazu versucht man, den letzten / vorletzten / vorvorletzten . Buchstaben zu erhöhen. Gruß pwm |
 |
|
es gibt imax Elemente, die sich wiederholen Der Zusammenhang ist: m-(l1-1)-...-(lmax-1)=n Aber gibts eine Idee für den zweiten Teil der Frage...? Auch wenn das kein rein mathematisches Problem ist...eher angewandte Mathematik |
|
|
|
Hallo warum ist die Idee der lexikographischen Auflistung aller Kombinationen nicht eine Antwort auf deine Frage? Gruß ledum |
|
|
|
Das habe ich noch nicht ganz verstanden könnten wir das mal am Beispiel AABBC durchexerzieren? |
|
|
|
Eigentlich ist mir nicht ganz klar, was genau du suchst. Du hast 9 Elemente, die Buchstaben von A bis I. Suchst du die Anzahl der Möglichkeiten, dir aus diesen 9 Elementen Elemente auszuwählen, wobei sich da natürlich einige wiederholen können? Wenn es dir dabei auf die Reihenfolge nicht ankommt, so spricht man von "Kombination mit Wiederholung" Wenn es dir auf die Reihenfolge ankommt, dann handelt es sich um eine "Variation mit Wiederholung" Oder hast du bereits deine Wahl von Buchstaben, unter denen sich manche auch mehrfache befinden, getroffen und möchtest nur wissen, auf wie viele Arten man diese anordnen kann? Da hast du ja für dein Beispiel bereits die richtige Lösung angegeben und hier spricht man von einer "Permutation mit Wiederholung". Was genau suchst du also - Permutation, Kombination oder Variation? Die Formeln dafür findest du sicher leicht (Kapitel: Kombinatorik) in deinen Unterlagen oder auch im Netz. Und Beispielprogramme dafür sollten auch leicht zu finden sind, denke ich. Jedenfalls wirst du im Knuth da sicher fündig. |
|
|
|
Eine Anmerkung insbesondere zum Fall (mit meine ich die Anzahl der auszuwählenden Elemente aus , bei dir also ): Jede Auswahl der entspricht eineindeutig einer Menge von nicht ausgewählten Elementen. D.h., die Betrachtung "9 aus 13" ist anzahlmäßig der Betrachtung "4 aus 13" äquivalent. Letzteres scheint im Abzählen etwas günstiger zu sein. P.S.: Ich gehe natürlich davon aus, dass du "Kombinationen" im üblichen Sinn meinst: D.h. Auswahlen ohne Berücksichtigung der Auswahlreihenfolge. |
|
|
|
Ich meine 2.) Also "Permutationen mit Wiederholung" Wobei mir die Begriffe: Variationen und Kombinationen und Permutationen natürlich vertraut sind. Aber "Permutationen mit Wiederholung" war mir nicht mehr geläufig Nun fehlt mir nur noch ein schlauer Algorythmus um (im Beispiel) nicht 88Milliarden Möglichkeiten (alle Permutationen) durchprobieren zu müssen um die (im Beispiel) 6,5 Millionen "Parmutationen mit Wiederholungen" zu finden. Dazu gab es das Stichwort "Lexikalischer Ansatz". Das hatte ich noch nichtganz verstanden. Könnte mir das mal jemand am Beispiel AABBC erklären? Da gibt es ja 120 Permutationen wovon nur übersichtliche 30 unterschiedlich sind. Mir geht es jetzt darum, den Algorythmus zu verstehen bzw zu finden (Teil 2 der Frage). Hintergrund ist natürlich eine Anwendung, ein Optimierungsproblem. Ich schreibe eine Software dazu. 7 Millionen Möglichkeitren durchzutesten geht noch. 87 Milliarden dauert Wochen...zumal die Tests (ist die Möglichkeit schon vorhanden?) sukzessive länger werden. |
|
|
|
Ich meine Also "Permutationen mit Wiederholung" Gut. Das heißt, die Elemente sind bereits ausgewählt und liegen vor. Dass diese aus einer 9-elementigen Menge gewählt wurden ist für die Aufgabe also irrelevant. Dir geht es nur darum, wie man diese Elemente anordnen kann. Was den Algorithmus anlangt - was spricht gegen eine Internetrecherche (sofern keine brauchbare Bibliothek zur Verfügung steht). Hier die ersten paar Links einer Suche: www.c-plusplus.net/forum/topic/178286/permutationen/2 www.java-forum.org/thema/permutation-mit-wiederholungen.126103 http//www.aconnect.de/friends/editions/computer/combinatoricode_g.html#Permutations_with_repetition_in_lexicographic_order |
|
|
|
Hallo, als altmodischer Mensch plädiere ich dafür, die Frage nach eine lexikografischen Anordnung selbst zu verstehen und zu lösen. Also was wäre zum Beispiel für ABACB das nächste Wort und wie kann man es systematisch finden? Gruß pwm |
1454557
1454500