matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenKombinatorikAnzahl Permutationen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Kombinatorik" - Anzahl Permutationen
Anzahl Permutationen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Anzahl Permutationen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

        
Bezug
Anzahl Permutationen: Antwort
Status: (Antwort) fertig Status 
Datum: 23:45 Sa 25.08.2012
Autor: reverend

Hallo HarryS, [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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]