Anzahl Belegungen ausrechnen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo allerseits!
Ich programmiere an einem Data-Mining Algorithmus und muss dabei die Größe eines Raumes ermitteln.
Ich habe eine Menge von n Elementen. Jedem Element ist eine Zahl zugeordnet, die die mögliche Anzahl der Ausprägungen/Belegungen des Elementes angibt.
Ich würde gerne wissen, wieviele mögliche Kombinationen der Elemente der Länge k unter Berücksichtigung der Belegungen möglich sind.
Wenn ich nur die Anzahl der Kombinationen der Länge k berechnen möchte, ist dies ja ganz einfach [mm] \vektor{n \\ k}. [/mm] Wie kann die Anzahl der Belegungen da eingehen?
Hier ein Beispiel zum verdeutlichen:
n = 6 (6 verschiedene Elemente)
n1 = 3, n2 = 5, n3 = 7, n4 = 4, n5 = 3, n6 = 4 (Anzahl der Belegungen für jedes ni)
Für die Kombination (n1, n2, n3) gäbe es also demzufolge noch 3*5*7=105 Belegungen.
Wie kann ich jetzt ermitteln, wieviele Kombinationen der Elemente unter Berücksichtigung dieser Belegungen existieren?
Vielen Dank!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:22 Fr 10.08.2012 | | Autor: | Teufel |
Hi!
Wie groß sind denn die Eingaben, die den Programm verarbeiten muss? Denn ich glaube, dass du wirklich jeweils über alle verschiedenen Wahlen von k Elementen aus n summieren musst, d.h. für n, k fest musst du immer eine Summe über [mm] \vektor{n \\ k} [/mm] Summanden bilden.
In Formeln: Sei f die Funktion, die du ausrechnen willst und [mm] N=\{n_1,\ldots,n_l\}, 0
Jetzt musst du dir nur noch überlegen, wie man diese Summe vernünftig implementieren kann. Für fixes $k$ kann man natürlich eine $k$-fach geschachtelte for-Schleife nehmen, aber da das $k$ ja beliebig sein kann, muss man sich wohl etwas anderes ausdenken (evtl. Rekursion? aber das kann natürlich bei großen Eingaben nach hinten losgehen).
|
|
|
|
