Kombinationen, Variationen, ...

[Atze]

Hi,

die Mathematik bietet für das Hantieren mit Permuationen, Kombinationen und Variationen in einem bestimmten Rahmen gutes Handwerkszeug. Ziehe n Objekte aus einem Vorrat von m. Mit Zurücklegen, ohne Zurücklegen, unter Beachtung der Reihenfolge oder auch nicht ...

Was ich bisher noch nicht gefunden habe, sind die Fälle, in denen es sich nicht um einen gemeinsamen Vorrat handelt, aus dem gezogen wird. Was ist z. B. mit Situationen, die einem Zahlensystem entsprechen, das nicht für jede Stelle den gleichen Zahlenvorrat nutzt? Ich denke dabei an sowas:

Es gibt 3 leere Plätze zu füllen. Für jeden dieser Plätze existiert ein eigener Kasten, aus dem unterschiedliche Kugeln gezogen werden können. Die Kästen enthalten dabei nicht zwangsweise die gleichen Kugeln. Wie lassen sich dafür die ganzen Erkenntnisse bzgl. Variationen aus dem einfachereren Fall eines gemeinsamen Vorrats übertragen? Für einige Teilfragen lassen sich relativ einfach Antworten finden. Geht's aber z. B. daran, Möglichkeiten auszuschließen, in denen die Reihenfolge der Kugeln in den 3 Plätzen keine Rolle mehr spielen soll, wird's haarig. Sind das dann Fälle, in denen sich eigentlich nur noch Brute-Force-Lösungen anbieten (d. h. alle Permuationen berechnen und anschließend aussortieren, was man nicht haben möchte)?

Kann vielleicht jemand mit entsprechenden Stichworten weiterhelfen?

Vielen Dank für die Hilfe

[Encoder]

Kannst du einen konkreten (nicht zu komplizierten) Fall beschreiben, für den du eine Lösung haben willst?
Aus deinen bisherigen Beschreibungen werd ich noch nicht schlau genug.

[Atze]

Hi,

Kannst du einen konkreten (nicht zu komplizierten) Fall beschreiben, für den du eine Lösung haben willst?
Aus deinen bisherigen Beschreibungen werd ich noch nicht schlau genug.

eigentlich interessiert mich vor allem der theoretische Teil. Für die praktische Anwendung kann ich mir ja immer eine Brute-Force-Lösung nach dem bereits erwähnten Prinzip bauen -- je nach Randbedingung auch etwas eleganter. Aber wenn Ihr ein konkretes Beispiel fürs Verständnis wollt, konstruiere ich mal Folgendes:

Gegeben seien 4 Zahlenmengen

M_1 = { 1, 2, 3 }
M_2 = { 2, 5, 6 }
M_3 = { 4 }
M_4 = { 5, 6, 7, 8, 9 }

und eine Menge M, die die Vereinigung dieser 4 Mengen darstellt.

M = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Wieviele unterschiedliche 4-Tupel lassen sich erzeugen, wenn

1. das n-te Element eines Tupels nur Zahlen aus der Menge M_n enthalten darf

Bsp.: (1,2,4,5) ist ein gültiges Tupel für obige M_n, (1,2,3,5) hingegen nicht

und

2. keine Zahl aus M mehr als einmal in einem Tupel vorkommen darf (die einzelnen Elemente eines Tupels also stets unterschiedliche Zahlenwerte aufweisen müssen)

Bsp.: (1,2,4,5) ist ein gültiges Tupel, (1,5,4,5) hingegen nicht

und

3. "Duplikate" von Tupeln nicht mitgezählt werden, wobei sich ein "Duplikat" durch Umsortieren der Elemente eines schon gezählten Tupels ergibt?

Bsp.: (1,5,4,6) ist ein Duplikat von (1,6,4,5)

Läßt sich diese Anzahl für beliebige M_n als geschlossener mathematischer Ausdruck angeben oder läuft es immer auf Ausprobieren hinaus?

Muß nur 1) allein erfüllt sein, ist das nicht schwierig. Nimmt man jedoch die anderen beiden Bedingungen hinzu, sehe ich keinen Weg für eine Lösung, die man "einfach so als Formel hinschreiben" und ausrechnen kann. Möglicherweise hat sich die Mathematik damit ja schon beschäftigt, nur fehlen mir da kurze und knackige Stichworte für die Suche.

Hilft das fürs Verständnis?

[Don P]

Hallo,

Gegeben seien 4 Zahlenmengen

M_1 = { 1, 2, 3 }
M_2 = { 2, 5, 6 }
M_3 = { 4 }
M_4 = { 5, 6, 7, 8, 9 }

und eine Menge M, die die Vereinigung dieser 4 Mengen darstellt.

M = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Wieviele unterschiedliche 4-Tupel lassen sich erzeugen, wenn [...]

Läßt sich diese Anzahl für beliebige M_n als geschlossener mathematischer Ausdruck angeben oder läuft es immer auf Ausprobieren hinaus?

Ein einziger Ausdruck dürfte nicht genügen. Man muss je nach gegebenen Grundmengen die Sache schon auf eine Kombination von Einzellösungen herunterbrechen, denke ich, also einen Algoritmus aus mehreren Schritten zusammenbauen.

So wie ich es verstehe, muss bei den gebenen Mengen z.B. zwingend eine 4 im Tupel vorkommen, aber eine 3 nicht unbedingt. Das hängt eben von den gegebenen Grundmengen ab und kann daher schwerlich in einem einzigen, allgemeingültigen Ausdruck angegeben werden.

Gruß, Don P

[Gunnar Bittersmann]

@@Atze:

nuqneH

M_1 = { 1, 2, 3 }
M_2 = { 2, 5, 6 }
M_3 = { 4 }
M_4 = { 5, 6, 7, 8, 9 }

Wieviele unterschiedliche 4-Tupel lassen sich erzeugen, wenn

1. das n-te Element eines Tupels nur Zahlen aus der Menge M_n enthalten darf

Das ist trivial. Da jeweils unabhängig voneinander aus den M_n ausgewählt wird: das Produkt der Anzahl der Elemente der M_n. In dem Fall 3 · 3 · 1 · 5 = 45.

2. keine Zahl aus M mehr als einmal in einem Tupel vorkommen darf (die einzelnen Elemente eines Tupels also stets unterschiedliche Zahlenwerte aufweisen müssen)

Es sind also die Tupel abzuziehen, in denen eine Zahl mehrfach vorkommt, hier die 2, 5 und 6.

Es gibt #M_3 · #M_4 = 1 · 5 = 5 Tupel mit zwei Zweien, #M_1 · #M_3 = 3 · 1 = 3 Tupel mit zwei Fünfen und ebenso viel mit zwei Sechsen. 45 - 5 - 3 - 3 = 34.

Qapla'

[DaBear]

2. keine Zahl aus M mehr als einmal in einem Tupel vorkommen darf (die einzelnen Elemente eines Tupels also stets unterschiedliche Zahlenwerte aufweisen müssen)

Es sind also die Tupel abzuziehen, in denen eine Zahl mehrfach vorkommt, hier die 2, 5 und 6.

Es gibt #M_3 · #M_4 = 1 · 5 = 5 Tupel mit zwei Zweien, #M_1 · #M_3 = 3 · 1 = 3 Tupel mit zwei Fünfen und ebenso viel mit zwei Sechsen. 45 - 5 - 3 - 3 = 34.

Hier mag das gehen. In einem Beispiel, indem aber mehrere Kombinationen möglich sind (z.b. (6,6,2,2)) darfst du nicht doppelt zählen. Das muss bedacht werden.

[Der Martin]

Hallo,

Ich denke dabei an sowas:
Es gibt 3 leere Plätze zu füllen. Für jeden dieser Plätze existiert ein eigener Kasten, aus dem unterschiedliche Kugeln gezogen werden können. Die Kästen enthalten dabei nicht zwangsweise die gleichen Kugeln.

du hast also beispielsweise eine Kiste mit Socken in 5 Farben, eine Kiste mit T-Shirts in 8 Farben, und eine Kiste mit Mützen in 6 Farben, und möchtest jetzt alle möglichen Kombinationen?
Oder hab ich das falsch verstanden? - Denn das wäre doch trivial ...

Wie lassen sich dafür die ganzen Erkenntnisse bzgl. Variationen aus dem einfachereren Fall eines gemeinsamen Vorrats übertragen?

Oh, verdammt, schon hinkt mein Beispiel. Ein Paar Socken lässt sich schlecht durch eine zweite Mütze ersetzen ...

Geht's aber z. B. daran, Möglichkeiten auszuschließen, in denen die Reihenfolge der Kugeln in den 3 Plätzen keine Rolle mehr spielen soll, wird's haarig. Sind das dann Fälle, in denen sich eigentlich nur noch Brute-Force-Lösungen anbieten (d. h. alle Permuationen berechnen und anschließend aussortieren, was man nicht haben möchte)?

Ich schließe mich Encoder an: Anschauliche Beschreibung bitte, eventuell Beispiele.

Ciao,
 Martin