Permutationen über Teilmengen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:47 Sa 02.11.2013 | | Autor: | samMumm |
Hallo,
nachdem die Software die Meinung vertritt das sei mein erster Beitrag in diesem Forum, möchte ich darauf hinweisen dass:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Nachdem jetzt die Formalien erledigt sind würde ich gerne auf mein Problem zu sprechen kommen, den ein Freund kam heute mit einem im ersten Augenblick recht einfachen Problem auf mich zu bei dem ich aber recht schnell einsehen musste das ich trotz fortgeschrittenen Hochschulstudium ziemlich auf Granit beiße.
Das Problem besteht darin für n-Teilmengen alle Permutationen zu finden so das an der n-ten Position in einer Permutation ein Element aus der n-ten Menge steht
Beispiel:
3 Teilmengen:
[mm] M_{1} [/mm] = { 1, 2, 3 }
[mm] M_{2} [/mm] = { 5, 6, 7 }
[mm] M_{3} [/mm] = { 8, 9, 0 }
Gültige Permutationen wären z.B.
(1, 5, 8 )
(1, 6, 0)
(2, 8, 9)
...
Vielleicht hätte ja jemand einen Tipp für mich wie man das Problem angehen könnte, den letzten endes soll es auf ein Programm hinauslaufen das dies durchführt und alle gültigen Permutationen liefert.
Ich hoffe ich bekomme jetzt nichts auf die Nase das ich ein Informatik-problem in einem Mathe-Forum gepostet habe. Aber da ich weniger Probleme in der Umsetzung als eher im finden eines Ansatz sehe denke ich das ich hier besser aufgehoben bin.
Ich würde mich auf jeden Fall über die eine oder andere Antwort freuen.
Viele Grüße
Dan
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:36 Sa 02.11.2013 | | Autor: | Marcel |
Hallo Dan,
> Hallo,
>
> nachdem die Software die Meinung vertritt das sei mein
> erster Beitrag in diesem Forum, möchte ich darauf
> hinweisen dass:
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Nachdem jetzt die Formalien erledigt sind würde ich gerne
> auf mein Problem zu sprechen kommen, den ein Freund kam
> heute mit einem im ersten Augenblick recht einfachen
> Problem auf mich zu bei dem ich aber recht schnell einsehen
> musste das ich trotz fortgeschrittenen Hochschulstudium
> ziemlich auf Granit beiße.
> Das Problem besteht darin für n-Teilmengen alle
> Permutationen zu finden so das an der n-ten Position in
> einer Permutation ein Element aus der n-ten Menge steht
> Beispiel:
> 3 Teilmengen:
> [mm]M_{1}[/mm] = { 1, 2, 3 }
> [mm]M_{2}[/mm] = { 5, 6, 7 }
> [mm]M_{3}[/mm] = { 8, 9, 0 }
>
> Gültige Permutationen wären z.B.
> (1, 5, 8 )
> (1, 6, 0)
> (2, 8, 9)
> ...
soweit ich das sehe, hat das aber nichts mit Permutationen zu tun (weißt
Du, wie eine Permutation definiert ist? Das ist eine bijektive Abbildung
einer Menge in sich).
Das hier ist doch eher sowas:
Vorgegeben seien [mm] $n\,$ [/mm] Mengen, etwa [mm] $M_1,...,M_n\,.$ [/mm] (Da ist dann schon die erste
Frage: Wie behandelt der fragende Informatiker Mengen, also in welcher
"Struktur" werden die abgespeichert?)
Dabei ist $n [mm] \in \IN$ [/mm] und jede Menge [mm] $M_k$ ($k=1,...,n\,$) [/mm] ist endlich. Damit kann man [mm] $M_k$ [/mm]
als "durchnummerierte Menge" annehmen.
Jetzt würde ich mir quasi mal ein Baumdiagramm hinmalen, sagen wir mal,
es sei [mm] $M_1=\{m_1(1),m_1(2)\},$ $M_2=\{m_2(1),m_2(2), m_2(3), m_2(4)\}$ [/mm] und [mm] $M_3=\{m_3(1),m_3(2), m_3(3)\}\,.$
[/mm]
(Die Elemente sollen innerhalb der Mengen paarweise verschieden sein,
d.h. [mm] $M_1$ [/mm] soll 2 Elemente, [mm] $M_2$ [/mm] 4 Elemente und [mm] $M_3$ [/mm] 3 Elemente haben!)
Dann siehst Du ja, dass es hier
[mm] $2*4*3=24\,$ [/mm] Tripel
gibt und dann kann man sich überlegen, wie man das möglichst in eine,
wie auch immer geartete Schleife, einbauen kann.
Eine Idee (wie man die algorithmisch umsetzt, kannst Du ja mal selbst
überlegen), wie so ein Algorithmus aussehen kann:
[mm] $BK_n$ [/mm] sei die Menge der bisherigen Kombinationen.
Bei Beginn des Alg.:
[mm] $BK_n \leftarrow \varnothing$
Nun nehmen wir die ersten n-Tupel in $BK_n$ auf, welche so gestrickt seien:
Die ersten $n-1$ Einträge sind das erste Element der entsprechenden Menge,
der $n\,$-te Eintrag durchläuft die Menge $M_n$
Also:
for $k=1$ to $|M_n|$ do
$\{$
$BK_n \leftarrow BK_n \cup \left\{\vektor{m_1(1)\\m_2(1)\\.\\.\\.\\m_{n-1}(1)\\m_n(k)}\right\}$
$\}$
So, und jetzt musst Du halt für jeden Vektor aus $BK_n$ die vorletzte Komponente
die Menge $M_{n-1}$ durchlaufen lassen und die neuen Vektoren in $BK_n$
aufnehmen usw. usf..
Ergänzung:
Dabei ist $m_k(j)$ "das $j\,$-te Element der Menge $M_k=\{m_k(1),...,m_k(|M_k|)\}$",
wobei $|M_k|$ die Anzahl der Elemente von $M_k$ bezeichne.
So erzeugst Du dann insgesamt
$|M_1|*...*|M_n|$
Vektoren.
P.S. Die Idee kann man sich gut am Baumdiagramm klarmachen, oder halt
mit Überlegungen der Kombinatorik:
Bei den n-Tupeln kann
an der ersten Stelle jedes Element der Menge $M_1$ auftauchen,
an der zweiten Stelle jedes Element der Menge $M_2,$
.
.
.
an der n-ten Stelle jedes Element der Menge $M_n.$
P.S. Du kannst natürlich auch sagen: In $BK_n$ nehme ich erstmal den Vektor
auf, der an jeder Stelle das erste Element der "zugehörigen Menge"
stehen hat. Ich schreibe jetzt einfach mal $(i,j,k)$ anstatt $\vektor{m_1(i)\\ m_2(j)\\ m_3(k)}$ mit
den obigen Mengen $M_1, M_2, M_3$ (aus dem BLAU MARKIERTEN BEREICH!)
Dann startet man also mit
$BK_3=\{(1,1,1)\}$
$M_3$ hat hier 3 Elemente, also kommt man zu den Tripeln
$(1,1,1),\;(1,1,2),\;(1,1,3)$
und damit bekommen wir $BK_3$ geupdatet zu
$BK_3=\{(1,1,1),\;(1,1,2),\;(1,1,3)\}$
(genauer: $BK_3=\left\{\vektor{m_1(1)\\m_2(1)\\m_3(1)},\;\vektor{m_1(1)\\m_2(1)\\m_3(2)},\;\vektor{m_1(1)\\m_2(1)\\m_3(3)}\right\}$)
Jetzt durchlaufen wir für jeden Vektor des (geupdateten) $BK_3$ die zweite
Komponente ($M_2$ hatte hier 4 Elemente)
$(1,1,1)$ betrachten:
$(1,1,1),\;\red{(1,2,1),\;(1,3,1),\;(1,4,1)}$
(die roten Elemente sind neu und werden (später!) in $BK_3$ aufgenommen $\to$ zwischenspeichern )
$(1,1,2)$ betrachten:
$(1,1,2),\;\red{(1,2,2),\;(1,3,2),\;(1,4,2)}$
(die roten Elemente sind neu und werden (später!) in $BK_3$ aufgenommen)
Analog noch für $(1,1,3)$
Am Ende dieses Schritts haben wir also
$BK_3=\{(1,1,1),\;\red{(1,2,1),\;(1,3,1),\;(1,4,1)},(1,1,2),\;\red{(1,2,2),\;(1,3,2),\;(1,4,2)}, (1,1,3),\;\red{(1,2,3),\;(1,3,3),\;(1,4,3)}\}$
usw. usf.
P.P.S. Offensichtlich kann man sich hier bei meiner Vorgehensweise noch
ein paar Kleinigkeiten sparen (schon vorhandene Elemente brauchen
nicht "nochmal" kreiert zu werden) und den kann man sicher auch optimieren
(alternative Vorgehensweise für "Zwischenspeichern" implementieren!)
Gruß,
Marcel
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:00 So 03.11.2013 | | Autor: | Marcel |
Nebenbei: Die Namensgebung ist vielleicht "komisch", aber bei [mm] $BK_n$ [/mm] dachte
ich einfach an
"Bisherige Kombinationen von [mm] $\red{n}$-Tupeln" [/mm] (ein [mm] $n\,$-Tupel [/mm] kann auch einfach als
"Vektor" mit [mm] $n\,$ [/mm] Einträgen gesehen werden)
Nur, damit das nicht so ganz magisch wirkt. 
|
|
|
|
