alle Kombinationen finden

Hallo

Sicherlich kennen die meisten den mathematischen Ausdruck "n über k".
Bsp:

Aus einem String der Länge 5 sollen alle möglichen Zeichenketten der Länge 3 gebildet werden.

Dies soll jedoch mit beliebigen Anzahlen von Zeichen möglich sein.
Mein Problem: Gibt es dazu einen Algorithmus?

elise

lös es auf:

5 über 3 sind

5!
--------
(5-3)! * 3!

Yankee

n über k lässt aber Mehrfachnennungen aussen vor, soweit ich weiss.l

Taurin

Möchtest du die Anzahl der Kombinationen? Mit oder ohne Beachtung der Reihenfolge? Mit oder ohne "Zurücklegen"?

Also angenommen ich habe 5 Kugel die von 1 bis 5 durchnummeriert sind, und ich will jetzt alle möglichen 3er Kombinationen finden.
Dann habe ich ja für die erste Kugel 5, für die zweite 4 und für die dritte 3 Möglichkeiten, also ohne Zurücklegen:
543
542
541
....

Wie kann ich all diese Paare per Algorithmus finden?

wenn Reihenfolge egal (d.h 1-2-3 == 1-3-2)

for(int i = 0; i < anz-2; ++i)
for(int i2 = i+1; i2 < anz-1; ++i2)
for(int i3 = i2+1; i3 < anz; ++i3) {
// loesung == i; i2; i3
}

wenn reihenfolge nich egal

for(int i = 0; i < anz; ++i)
for(int i2 = 0; i2 < anz; ++i2)
if(i2 != i)
for(int i3 = i2+1; i3 < anz; ++i3)
if(i3 != i2 && i3 != i) {
// loesung[2] == i; i2; i3
}

elise

sorry, ich hab zu schnell überflogen, du suchst die einzelnen strings, und nicht die anzahl... ich dachte zu schnell: die möglichkeiten.

@DasPinschh:
Danke, aber deine Lösung gilt ja nur für die Auswahl von 3 Elementen. Ich suche aber eine Lösung, die für eine beliebige Zahl n gilt.

bwinf? also ich habs rekursiv gelöst

die anzahl lösungen ist übrigens auch kein prob!
n aus k:
(k * (k-1) * (k-2) * ... (k-(n-1)) ) / n!

Edit: Prinzip bei ner rekursiven lösung ist gleich!

hi

kann einer mal beide verfahren testen und sagen was besser ist.
bei der rekursiven wird ja viel mehr speicher verwendet.
die Fibon. zahlen sind glaube ich rekursiv langsamer(programm geschwindigkeit ab fib(30)z.b. ) als die nicht-rek.

mata

Wenn es eine einfache iterative Lösung gibt, ist diese fast immer vorzuziehen, weil das Betriebssystem bei Rekursion doch ne ganze Menge Overhead hat und auch eine Rekursion letzten Endes in eine Iteration überführen muss, um sie auszuführen. Beim Beispiel Fibonakki Zahlen oder Fakultät gibts ja auch ne simple iterative Lösung, aber Türme von Hanoi kann nur recht kompliziert iterativ gelöst werden.

Gruß,

mata