Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten |
18.04.2012, 13:44 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten Hallo allerseits, ich bin auf der Suche nach der Formel zur Bestimmung der Anzahl der Permutationen im folgendem Fall: Ziehen von k Elementen aus einer Menge mit n Elementen, wobei n_1 Elemente vom Typ1, n_2 Elemente vom Typ2, ... und n_k Elemente vom Typk sind und n = n_1 + n_2 + ... + n_k gilt. Kann mir irgendeiner weiterhelfen? Vielen Dank! Nils Meine Ideen: Mein Ansatz ohne Abhängigkeit von k lautet: P_n = n!/ (n_1!*...*n_k!) Mein Ansatz in Abhängigkeit von k ist folgender: P_n = P_n/ (n-k)! <-- Das ist aber falsch, oder? |
|||||||||||
19.04.2012, 10:24 | Mystic | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Das wäre die Antwort auf die Frage, wieviele Möglichkeiten es gibt, n Elemente zu ziehen, wenn zwischen Elementen des gleichen Typs nicht unterschieden wird... War hier nur leider nicht gefragt...
Das ist überhaupt totaler Unsinn, denn hier kann man ja durch P_n dann kürzen und erhält dann die (jetzt nicht besonders sinnvolle! ) Gleichung (n-k)!=1 woraus k=n oder k=n-1 folgt... |
|||||||||||
19.04.2012, 10:29 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten Mein Ansatz in Abhängigkeit von k ist folgender: P_n = (n!/ (n_1!*...*n_k!))/ (n-k)! |
|||||||||||
19.04.2012, 10:42 | Mystic | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Damit kann leider auch nichts anfangen... Deine Formel liefert ja für nicht einmal eine ganze Zahl... Wieviele Möglichkeiten gibt es denn für die k gezogenen Elemente, was jetzt nur einmal ihren Typ betrifft? |
|||||||||||
19.04.2012, 11:05 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten Ok entschuldige, habe gerade noch etwas entdeckt. P_n = (n!/ (n_1!*...*n_j!))/ (n-k)! Bsp: n = 5 j = 3 (also 3 verschiedene Typen von Objekten) n_1 = 1 n_2 = 2 n_3 = 2 k = 2 P_n = 5!/(2!*2!*1!)/(5-2)! = 5 Es müssten aber in diesem Beispiel P_n = 10 sein. |
|||||||||||
19.04.2012, 11:19 | Mystic | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Hm, was genau hast du entdeckt? Dass vielleicht deine Angabe
falsch ist? Denn da kommt kein j darin vor... Außerdem funktioniert mein Gegenbeispiel (mit k=j) ja noch immer... |
|||||||||||
Anzeige | |||||||||||
|
|||||||||||
19.04.2012, 11:23 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten Ziehen von k Elementen aus einer Menge mit n Elementen, wobei n_1 Elemente vom Typ1, n_2 Elemente vom Typ2, ... und n_j Elemente vom Typj sind und n = n_1 + n_2 + ... + n_j gilt. P_n = (n!/ (n_1!*...*n_j!))/ (n-k)! Bsp: n = 5 j = 3 (also 3 verschiedene Typen von Objekten) n_1 = 1 n_2 = 2 n_3 = 2 k = 2 P_n = 5!/(2!*2!*1!)/(5-2)! = 5 Wo liegt der Fehler? Es müssten aber in diesem Beispiel P_n = 10 sein. |
|||||||||||
19.04.2012, 12:00 | Mystic | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Ich versteh immer nur Bahnhof... Du hast doch hier 3 Typen, nenen wir sie x, y und z und "langst" zweimal zu, wobei du dich beim Typen x nur einmal "bedienen" darfst... Es geht also hier darum, dass Polynom auszumultiplizieren und alle Ausdrücke abzuzählen (d.h., deren Koeffizienten aufzusummieren), welche den Faktor nicht enthalten... Da komm ich aber nicht auf 10... |
|||||||||||
19.04.2012, 12:40 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten Ok, ich habe eine Menge n (n=5) in einer Urne besipielsweise und ziehe k (k=2) Mal. Angenommen ich habe die Elemente A, B und C und im Beispielfall n={A,B,B,C,C} Elemente in der Urne. Ziehe ich jetzt zwei mal bekomme ich maximal folgende Kombinationen: P(n) = {AB,AC,BA,BB,BC,CA,CB,CC} Und genau hierfür suche ich eine allgemeingültige Formel zur Beschreibung der Anzahl möglicher Permutationen. |
|||||||||||
19.04.2012, 12:52 | Mystic | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Hm, warum wiederholst du nochmals, aber mit deinen Worten, was ich oben schon gesagt habe? Wenn man mein Polynom ausmultipliziert, bekommt man doch wobei hier das Monom "nicht erlaubt" ist... Du musst also dann in das Polynom nur einsetzen, um für dein Beispiel auf die Anzahl der Möglichkeiten zu kommen... |
|||||||||||
19.04.2012, 13:11 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten ok, und wie setze ich das zu einer allgemein Formel zusammen und ? |
|||||||||||
19.04.2012, 13:27 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten Das scheint unglaublich schwer in einer geschlossenen Formel erfassbar zu sein. Im Fall, dass nur die Auswahlen ohne Berücksichtigung der Reihenfolge interessieren, d.h. hier etwa {AB,AC,BB,BC,CC} findet man noch ein halbwegs brauchbares Siebformel-Ungetüm. Aber hier, mit Berücksichtigung der Reihenfolge ... |
|||||||||||
19.04.2012, 13:34 | Mystic | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Ja, tatsächlich habe ich nach näherer Betrachtung der Aufgabe auch sofort an dich und deine Vorliebe für die "Siebformel" gedacht... Ich habe allerdings schwer den Verdacht, dass der Threadersteller eine (oder mehrere ) konkrete Aufgaben dieser Art lösen sollte, und glaubte, besonders schlau zu sein, wenn er die Aufgabe gleich allgemein stellt, wodurch sie dann viel zu schwer bzw. unlösbar wird... |
|||||||||||
19.04.2012, 14:09 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten Ich benötige schon eine allgemeine Aussage, ansonsten hätte ich hier keine Frage formuliert. Für k = n kann ich ja folgende allgemeine Formel für die Anzahl der Permutaionen definieren: P(n) = (n_1+n_2+...*n_j)! / n_1! * n_2! * ... * n_j! Weiterhin müsste ich "nur" noch die Abhängigkeit von k mit in den Nenner hineinbringen. |
|||||||||||
19.04.2012, 15:23 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Das stellst du dir so vor, dass das so einfach gehen könnte. Ist es aber nicht. |
|||||||||||
19.04.2012, 15:36 | Mystic | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
"Nur" ist gut, denn der Fall k=n ist ein trivialer Sonderfall, der nichts über die Schwierigkeit des eigentlichen Problems aussagt... Ich bleibe dabei: Es handelt sich dabei um ein von dir selbst gestelltes Problem, im naiven Glauben, dass eine einfache Verallgemeinerung des obigen Spezialfalls leicht möglich sein müsste... "Instanzen" dieses Problems, also mit konkreten Zahlenangaben, sollten jedoch im Gegensatz dazu kein Problem darstellen.. PS: Crossposting ist hier übrigens gar nicht gern gesehen... |
|||||||||||
19.04.2012, 16:12 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Nehmen wir den Fall . Da gibt es dann AB , AC , BA , BC , CA , CB , CC also genau 7 Varianten. Wie bitte soll die Anzahl 7 bei Division von durch irgendwas Ganzzahliges entstehen? Oder überhaupt bei der Division von durch eine ganze Zahl? Dieses einfache Beispiel zeigt also schon, dass es absurd ist, an eine Formel derart einfacher Struktur zu glauben. P.S.: Hier mal noch die angedachte Anzahlformel für den Fall von ungeordneten Auswahlen (d.h. ohne Berücksichtigung der Auswahlreihenfolge): Das ist als Indikator zu verstehen (=1 wenn die Bedingung erfüllt ist; =0 sonst).
Soll er es doch versuchen, dann wird er sehen, dass dort auch nur mit Wasser gekocht wird. |
|||||||||||
19.04.2012, 16:25 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten Ok ein praktischer Fall wäre: n = 150 j = 25 k=40 n_1 =2 n_2 =9 n_3 =5 n_4 =4 n_5 =9 n_6 =10 n_7 =8 n_8 =5 n_9 =5 n_10 =4 n_11 =5 n_12 =8 n_13 =10 n_14 =8 n_15 =5 n_16 =2 n_17 = 9 n_18 = 5 n_19 = 2 n_20 = 8 n_21 = 9 n_22 = 4 n_23 = 5 n_24 = 4 n_25 = 5 Da ich das nicht ausrechnen möchte, war ich auf der Suche nach einer Verallgemeinerung. Es ist schon unglaublich wie schnell hier die Leute ausfallend werden... |
|||||||||||
19.04.2012, 16:27 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
|
|||||||||||
19.04.2012, 16:43 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Die Frage hatte ich vor der ersten Antwort hier gestellt in der Hoffnung, dass mir irgendwer weiterhelfen kann.
Eine einfache Antwort, dass es zu komplex und nicht leicht lösbar ist hätte mir auch gereicht... Trotzdem danke. |
|||||||||||
19.04.2012, 18:38 | Mystic | Auf diesen Beitrag antworten » | |||||||||
RE: Kombinatorik: Anzahl Permutationen von klassenweise äquivalenten Objekten
Ich hätte das jetzt noch nicht als "ausfallend" eingestuft, aber wenn das so rüberkam, entschuldige ich mich dafür... Was dein Beispiel betrifft, ist mir das echt auch zu krass... Aber ich denke, dass ich möglicherweise sowas wie eine Formel gefunden habe, die ich an folgenden einfacheren Beispiel demonstrieren möchte: Mein Polynom schaut dafür so aus: und man muss wieder nur einsetzen, um auf die gesuchte Anzahl zu kommen... Das Ganze kommt mir jetzt fast ein bißchen zu einfach vor, daher hoffe ich, ich habe mich da nirgends "vergaloppiert"... |
|||||||||||
19.04.2012, 18:50 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Ich hab meine Zweifel, dass das stimmt: In deinen Polynomen sind ja so siebformelähnliche Strukturen erkennbar: steht für alle 10er-Tupel ohne Anzahlbeschränkung bei den vier Typen. Wofür aber steht etwa ? Meines Erachtens nur für dreimal Element 1 an den ersten drei (oder drei anderen vorab festgelegten (!)) Positionen, und die anderen sieben Positionen sind wieder freigegeben. Das ist aber nicht ganz das, was wir hier wollen, oder? Wir wollen hier doch mindestens dreimal Element 1, ohne Festlegung der Positionen... |
|||||||||||
19.04.2012, 18:55 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Ja, ist mir eben auch aufgefallen... Da muss natürlich jeweils ein Koeffizient hin, der die Anzahl der Möglichkeiten für die jeweilige Auswahl beschreibt... Das würde also dann ergeben, wenn ich mich nicht schon wieder geirrt habe... |
|||||||||||
19.04.2012, 19:14 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Nein, jetzt zählst du wieder einige Tupel mehrfach - es ist m.E. so nicht zu retten. Nehmen wir mal den Fall von neunmal Element 1 und einmal Element 2. In deinem Polynom steht dafür der Anteil , es müssten doch aber sein, oder irre ich mich da? Das jetzt mit zu multiplizieren, bringt es auch nicht. Die Sache ist teuflisch, das hatte ich oben versucht anzudeuten. EDIT: M.E. bleibt dir nur, Tippel-Tappel-Tour alle möglichen Anzahlen von Element 1 da einzeln durchzugehen, also bzw. was sich dann eher lohnen würde Das wäre also nur die Korrektur zu deinem Term - die Sache wächst zu einem wahren Monstrum. |
|||||||||||
19.04.2012, 19:51 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Ja, ich fürchte, ich habe da jetzt wohl selber gemacht, was ich den Fragestellern hier oft vorwerfe, nämlich "aus der Hüfte zu schiessen"... Was du sagst stimmt natürlich, für einen Moment dachte ich, es sei doch nicht ganz so kompliziert... Aber das ist es wirklich, was damit wohl hinlänglich bewiesen ist... Edit: Immerhin sollte die Idee dahinter noch für eine einfache Berechnung mittels eines CAS nutzbar sein... Jedenfalls habe ich den Term
in Maple15 eingegeben und es hat daraufhin die Zahl 465387 ausgespuckt... |
|||||||||||
19.04.2012, 20:34 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Nochmal zu der Anzahl oben, die kann man nämlich auch so interpretieren: Es gibt insgesamt -Tupel ganzer Zahlen mit der Eigenschaft für sowie . Jedem dieser -Tupel entspricht nun eine ungeordnete, sowie geordnete Elementfolgen. D.h., du müsstest über alle dieser -Tupel den Wert summieren, um auf die gewünschte Anzahl zu kommen. Für
ist die Anzahl der Fälle, über die da summiert werden müsste. Auch unter Einbeziehung einiger Symmetrien und daraus folgender Zusammenfassungen bleibt immer noch ein ganz ordentlicher Hammer, das möchte ich meinem PC nicht zumuten, solange hält der (und sicher auch ich) nicht durch. |
|||||||||||
19.04.2012, 21:44 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Ja, allerdings habe ich inzwischen einen anderen Weg für die Berechnung mittels einem CAS gefunden, den ich oben für "mein" Beispiel hineineditiert habe... Wenn diese Ergebnis stimmt (was mittels brute force noch überprüfbar sein sollte), dann ich sehe ich auch für die Originalaufgabe des Threaderstellers eine Chance... |
|||||||||||
19.04.2012, 21:47 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Diesmal zweifle ich nicht die Formel an, sondern dass das bei dem Datensatz in erträglicher Zeit machbar ist.
Den Wert kann ich mittels MuPAD-Skript
|
|||||||||||
20.04.2012, 11:07 | nils2012 | Auf diesen Beitrag antworten » | |||||||||
Hallo, vielen Dank für all Eure Mühen. Ich denke, dass ich mit diesen Ansätzen etwas anfangen kann. |
|||||||||||
20.04.2012, 12:11 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Damit hast du leider recht... Ich habe inzwischen aus dem Maple-Program noch alles rausgeholt, was meiner Meinung nach drinnen war, und es schaut nun so aus
Im wesentlichen ist es also wieder einmal der "Square and Multiply"-Algorithmus, wobei es nur darum geht, die Potenz zu bilden und dabei schon zwischendurch immer alle (in Hinblick auf die vorgegebenen Restriktionen) "unzulässigen" Monome zu entfernen... Es liefert dann auch tatsächlich für "mein" Beispiel wieder das korrekte Ergebnis (danke übrigens für dessen Überprüfung! ), stürzt dann aber leider bei der eigentlichen Aufgabe auf meinem PC wegen Speicherüberlaufs ab...
Ja, ich denke, mehr als diese Lösungsansätze ist da wirklich nicht drinnen, insbesondere keine wirklich befriedigende Formel ... Es ist aber im Prinzip nicht schwer, das für einen konkreten Fall auch wirklich auszurechnen, da bleib ich dabei, aber dein Beispiel ist dafür einfach zu "groß"... |
|||||||||||
20.04.2012, 14:52 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Dann mal noch die langsame MuPAD-Variante - ich bevorzuge ja eigentlich C/C++, hatte jetzt aber keine Lust, mich um eine BigInteger-Bibliothek zu kümmern:
Berechnungsdauer ca. 6 Sekunden, aber das Beispiel ist ja auch etwas größer. |
|||||||||||
20.04.2012, 16:15 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Ja, das bekomm ich auch heraus, allerdings erst nach 89.7s... Wenngleich ich mich jetzt nicht vorrangig um Aspekte der Rechengeschwindigkeit gekümmert habe, sondern es mir mehr darum ging, meinen hier skizzierten Lösungsweg möglichst genau umzusetzen, so ist die Performance deines Programms schon recht beeindruckend... |
|||||||||||
20.04.2012, 16:44 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Egal ob 6 oder 89 Sekunden - man kann sich jetzt schon vorstellen was passiert, wenn man die Algorithmen auf den vollen 25-dimensionalen Anzahlvektor loslässt. Speicherplatzprobleme hab ich da zwar nicht, aber ... das hatte ich ja oben schon gesagt: Zu wenig Lebenszeit. |
|||||||||||
20.04.2012, 20:48 | Mystic | Auf diesen Beitrag antworten » | |||||||||
Leider ist - aus meiner Sicht - der Unterschied noch viel dramatischer... Ich habe jetzt dein Programm in den Maple Editor hinüberkopiert und da und dort ein bißchen adaptiert:
Und siehe da, es läuft auf meinem Rechner sogar 10 mal so schnell, d.h., dein Algorithmus ist für dieses Beispiel mehr als 100 mal schneller... |
|||||||||||
20.04.2012, 20:56 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||||
Wahrscheinlich hat dein Maple deutlich effizientere Routinen bei der Berechnung großer Integerzahlen - na egal. Nachtrag: Die C-Variante unter Nutzung der GMP (Sektion "Integer Functions") schlägt sich mit Berechnungszeit <20 ms erwartungsgemäß gut bei obigem Beispiel. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|