Kominationen, keine Permutationen erlaubt

29.12.2006, 15:34

Kominationen, keine Permutationen erlaubt

Erstmal, ich hab' keinen Schimmer von Stochastik, aber interessiere mich für die Lösung des folgenden Problems:

Es sind die $\begin{eqnarray*} n \end{eqnarray*}$ Zahlen $\begin{eqnarray*} a_1,a_2,a_3...a_n \end{eqnarray*}$ gesucht, die folgendes erfüllen:

$\begin{eqnarray*} a) \end{eqnarray*}$ Die Summe aller Zahlen ist $\begin{eqnarray*} \leq n \end{eqnarray*}$ (das konnte ich ja noch einfach erklären)

$\begin{eqnarray*} b) \end{eqnarray*}$ Jetzt wird's kompliziert, da ich den Fachausdruck dafür nicht kenne. Deshalb erklär' ich's an einem Beispiel:

Für $\begin{eqnarray*} n=3 \end{eqnarray*}$ wäre zum Beispiel eine Kombination meiner Lösung (1) $\begin{eqnarray*} (1,1,0) \end{eqnarray*}$ da $\begin{eqnarray*} 2<3 \end{eqnarray*}$ ist, aber $\begin{eqnarray*} (1,0,1) \end{eqnarray*}$ soll nicht mehr als Lösung auftauchen, da das ja nur 'ne andere Anordnung von (1) ist. $\begin{eqnarray*} (1,1,1) \end{eqnarray*}$ darf aber wieder eine Lösung sein, da nicht mehr alle $\begin{eqnarray*} a \end{eqnarray*}$ gleich sind.

Vllt. war mein Beispiel ungünstig, Deshalb: $\begin{eqnarray*} a \end{eqnarray*}$ ist nicht nur $\begin{eqnarray*} \in (0,1) \end{eqnarray*}$ sondern kann alle Werte $\begin{eqnarray*} 0 \leq a \leq n \end{eqnarray*}$ annehmen.

Was ist jetzt eigtl. gesucht? Gesucht ist eine (oder mehrere) Funktion(en), die mir alle Kombinationen gemäß $\begin{eqnarray*} a) \end{eqnarray*}$ und $\begin{eqnarray*} b) \end{eqnarray*}$ ausgeben.

Boah, ich glaub' das versteht keiner, aber wusste nicht, wie ich es erklären kann. traurig

Kann man da was reißen?

Ich hab's bis $\begin{eqnarray*} n=7 \end{eqnarray*}$ mit 'ner Brutforceattacke probiert, aber bei Werten größer $\begin{eqnarray*} 7 \end{eqnarray*}$ wird's dann relativ unpraktisch. Zumindest in PHP. ^^

29.12.2006, 15:44

tigerbine

Auf diesen Beitrag antworten »

RE: Kominationen, keine Permutationen erlaubt
Frage1: Wie viele Stellen stehen jetzt in den Klammern (...,...) ?

Frage2: Aus welcher Menge stammen die Einträge?

29.12.2006, 15:49

Auf diesen Beitrag antworten »

RE: Kominationen, keine Permutationen erlaubt

Zitat:

Original von tigerbine
Frage1: Wie viele Stellen stehen jetzt in den Klammern (...,...) ?

In der Klammer stehen $\begin{eqnarray*} n \end{eqnarray*}$ Elemente.
Ich dachte zBsp. $\begin{eqnarray*} (a_1,a_2) \end{eqnarray*}$ ist 'n Tupel, $\begin{eqnarray*} (a_1,a_2,a_3) \end{eqnarray*}$ ist'n Tripel usw. Das meinte ich mit den Klammern..

Zitat:

Original von tigerbine
Frage2: Aus welcher Menge stammen die Einträge?

Wie oben steht $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} 0 \end{eqnarray*}$ .

Hoffe das hilft irgendwie. unglücklich

29.12.2006, 15:56

tigerbine

Auf diesen Beitrag antworten »

RE: Kominationen, keine Permutationen erlaubt
Ok, also n-Stellen mit erlaubten werten von 0 bis n, ja?

Kriterium 1: Summe der Eintrage kleiner gleich n

Kriterium 2: Die Tupel sind nicht geordnet. d.h. du bewertest nur wie oft eine Zahl vorkommt, nicht wann, ja?

Muss mal weg. Denke auf dem Weg drüber nach. Bis später!

edit: 0 ist dabei

29.12.2006, 16:02

Auf diesen Beitrag antworten »

RE: Kominationen, keine Permutationen erlaubt

Zitat:

Original von tigerbine
Ok, also n-Stellen mit erlaubten werten von 1 bis n, ja?

Nein, wäre $\begin{eqnarray*} 1 \end{eqnarray*}$ die kleinste zulässige Zahl, dann wäre die einzige Kombination immer $\begin{eqnarray*} (1,1,1,1,...,1) \end{eqnarray*}$ . Die kleinste Zahl ist $\begin{eqnarray*} 0 \end{eqnarray*}$ .

Zitat:

Original von tigerbine
Kriterium 1: Summe der Eintrage kleiner gleich n

Yes!

Zitat:

Original von tigerbine
Kriterium 2: Die Tupel sind nicht geordnet. d.h. du bewertest nur wie oft eine Zahl vorkommt, nicht wann, ja?

Die Forumlierung ist spitze. Freude

Da bin ich garnicht drauf gekommen. Hammer

Zitat:

Original von tigerbine
Muss mal weg. Denke auf dem Weg drüber nach. Bis später!

Ja, dann viel Spaß. Wär' super, wenn du da irgend'ne Idee hättest.

Gott

Edit: Mit viel Spaß meinte ich nicht: Viel Spaß mit der Aufgabe. Augenzwinkern

29.12.2006, 16:49

therisen

Auf diesen Beitrag antworten »

Hallo,

wenn man mal deine Bedingung 2 zunächst weglässt, interessierst du dich also für die Mächtigkeit der Menge $\begin{eqnarray*} A_n=\{(k_1,\ldots,k_n)\in \mathbb N_0^n\ |\ k_1+\ldots+k_n\leq n\} \end{eqnarray*}$ ?
Mit $\begin{eqnarray*} B_{n,m} := \{(k_1,\ldots,k_n)\in \mathbb N_0^n\ |\ k_1+\ldots+k_n= m\} \end{eqnarray*}$ könnte man vielleicht so rechnen: $\begin{eqnarray*} |A_n| = \left|\bigcup_{i=0}^n B_{n,i}\right| = \sum_{i=0}^n {n+i-1 \choose i} = \frac{(n+1){2n\choose n+1}}{n} \end{eqnarray*}$
Ohne Gewähr, muss jetzt erstmal weg.

Gruß, therisen

29.12.2006, 17:07

Auf diesen Beitrag antworten »

Verdammt. Das ist mir alles zu hoch. Wenn der Rest auch so komplziert ist, dann kann ich hier gleich einpacken. traurig

29.12.2006, 19:03

Auf diesen Beitrag antworten »

Suchst du wirklich nach allen ungeordneten n-Tupeln $\begin{eqnarray*} (a_1,a_2,\ldots,a_n) \end{eqnarray*}$ nichtnegativer ganzer Zahlen mit $\begin{eqnarray*} a_1+a_2+\cdots+a_n\leq n \end{eqnarray*}$ , oder doch nur nach der Anzahl derartiger $\begin{eqnarray*} n \end{eqnarray*}$ -Tupel ??? geschockt

Ersteres sollte doch kein größeres Problem sein, musst du eben ein Programm schreiben - natürlich ist das nur für einigermaßen kleine $\begin{eqnarray*} n \end{eqnarray*}$ praktikabel. Big Laugh

Geht es hingegen nur um die Anzahl: Wie's aussieht suchst du $\begin{eqnarray*} \sum_{k=1}^n p(k) \end{eqnarray*}$ mit der Partitionsfunktion $\begin{eqnarray*} p \end{eqnarray*}$ .

29.12.2006, 19:09

Auf diesen Beitrag antworten »

Danke Arthur. Leider geht es mir nicht um die Anzahl, aber ich schau' mir den Artikel trotzdem an.

Wie oben schon geschrieben, geht's ganz flott (und einfach) mit Brutforce bis $\begin{eqnarray*} n=7 \end{eqnarray*}$ . $\begin{eqnarray*} n=8 \end{eqnarray*}$ wäre auch noch okay. Alles andere dürfte ich dann aber nicht mehr in PHP realisieren und C++ ist mir jetzt zu aufwä(e?)ndig.

Neue Frage »

Antworten »

Kominationen, keine Permutationen erlaubt

Verwandte Themen