Anzahl Permutationen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:06 Sa 25.08.2012 | | Autor: | HarryS |
| Aufgabe | Die Aufgabe kommt aus einem Algorithmus zur nachträglichen Herstellung von Konsistenz in einer Datenbank. Nachdem das aber nichts zur Sache tut, will ich die Aufgabe in einen spielerischen Kontext setzen:
Ich habe n durchnummerierte "Hütchen". Diese n Hütchen sollen in allen Kombinationen auf m durchnummerierte "Plätze" gesetzt werden. Gefragt ist die Anzahl der möglichen Anordnungen die es bei gegeben n und m gibt. n ist kleiner gleich m . Wichtig: die Nummerierung muss immer erhalten bleiben, d.h. zwischen den Hütchen können zwar Plätze frei bleiben, sie bleiben aber immer in der durch die Nummerierung gegebenen Ordnung.
Beispiel: n = 3, m = 5, eine der gesuchten Anordnungen ist also z. B.
H1 H2 - - H3
P1 P2 P3 P4 P5 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich habe einen Algorithmus entwickelt der alle Permutationen generiert. Nachdem die Komplexität schnell platzt, will ich vorab berechnen auf wie viele Kombination das hinausläuft. Der Algorithmus ist rekursiv und funktioniert so:
Wenn die Anzahl der Hütchen gleich 0 ist, dann bin ich fertig, die Plätze bleiben alle leer.
Wenn die Anzahl der Hütchen gleich der Anzahl der Plätze ist, ebenfalls.
Ansonsten kann ich entweder das erste Hütchen auf den ersten Platz setzen und danach die n-1 Hütchen auf m-1 Plätze verteilen, oder ich setze kein Hütchen auf den ersten Platz und kann dann n Hütchen auf m-1 Plätze verteilen.
In der Informatik habe ich gelernt dass man das so ausdrücken kann (O = Komplexität):
O (n,m) = 1 [wenn n=0 oder n=m]
O (n,m) = O (n-1,m-1)+O (n, m-1)
Nachdem die Komplexitätsberechnung per Algorithmus so rekursiv zwar leicht zu berechnen ist, leider aber auch die gleiche Komplexität wie das Ursprungsproblem hat, suche ich eine Umformulierung der Komplexitätsberechnung ohne Rekursion.
Wie kann man also O (n,m) ohne Rekursion ausdrücken?
|
|
| |
|
Hallo HarryS, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Wenn man den "Trick" einmal kennt, ist die Berechnung gar nicht so schwer.
> Die Aufgabe kommt aus einem Algorithmus zur nachträglichen
> Herstellung von Konsistenz in einer Datenbank. Nachdem das
> aber nichts zur Sache tut, will ich die Aufgabe in einen
> spielerischen Kontext setzen:
>
> Ich habe n durchnummerierte "Hütchen". Diese n Hütchen
> sollen in allen Kombinationen auf m durchnummerierte
> "Plätze" gesetzt werden. Gefragt ist die Anzahl der
> möglichen Anordnungen die es bei gegeben n und m gibt. n
> ist kleiner gleich m . Wichtig: die Nummerierung muss immer
> erhalten bleiben, d.h. zwischen den Hütchen können zwar
> Plätze frei bleiben, sie bleiben aber immer in der durch
> die Nummerierung gegebenen Ordnung.
>
> Beispiel: n = 3, m = 5, eine der gesuchten Anordnungen ist
> also z. B.
>
> H1 H2 - - H3
> P1 P2 P3 P4 P5
Ok. Stell Dir vor, zu den n Hütchen kommen noch m-n nicht unterscheidbare Trennstäbe. Nur diese dürfen bewegt werden. Dann gibt es m Plätze, auf denen die m-n Trennstäbe liegen dürfen.
Dafür gibt es nach den Regeln der Kombinatorik [mm] \vektor{m\\m-n} [/mm] Möglichkeiten. Fertig.
> Ich habe einen Algorithmus entwickelt der alle
> Permutationen generiert. Nachdem die Komplexität schnell
> platzt, will ich vorab berechnen auf wie viele Kombination
> das hinausläuft. Der Algorithmus ist rekursiv und
> funktioniert so:
>
> Wenn die Anzahl der Hütchen gleich 0 ist, dann bin ich
> fertig, die Plätze bleiben alle leer.
> Wenn die Anzahl der Hütchen gleich der Anzahl der Plätze
> ist, ebenfalls.
> Ansonsten kann ich entweder das erste Hütchen auf den
> ersten Platz setzen und danach die n-1 Hütchen auf m-1
> Plätze verteilen, oder ich setze kein Hütchen auf den
> ersten Platz und kann dann n Hütchen auf m-1 Plätze
> verteilen.
>
> In der Informatik habe ich gelernt dass man das so
> ausdrücken kann (O = Komplexität):
>
> O (n,m) = 1 [wenn n=0 oder n=m]
> O (n,m) = O (n-1,m-1)+O (n, m-1)
>
> Nachdem die Komplexitätsberechnung per Algorithmus so
> rekursiv zwar leicht zu berechnen ist, leider aber auch die
> gleiche Komplexität wie das Ursprungsproblem hat, suche
> ich eine Umformulierung der Komplexitätsberechnung ohne
> Rekursion.
>
> Wie kann man also O (n,m) ohne Rekursion ausdrücken?
Siehe oben. Du bist hoffentlich mit Binomialkoeffizienten vertraut.
Wenn nicht:
[mm] \vektor{n\\m-n}=\bruch{n!}{(m-n)!(2n-m)!}
[/mm]
wobei das Aurufungszeichen für die Fakultät steht: [mm] k!=\produkt_{i=1}^k{i}
[/mm]
Für große Fakultäten gibt die Stirlingformel eine gute Näherung. Oft kann man damit auch noch die Größenordnung von Binomialkoeffizienten bestimmen, die man vollständig nicht mehr bestimmen kann, weil (in der obigen Rechnung) schlicht n! zu groß wird.
Grüße
reverend
|
|
|
|
