Kombinations-Generator

[Shooter]

Hallöchen,

Ich habe eine variable Anzahl von Zeichen, beispielsweise DAELN. Nun brauche ich einen Algorithmus, der mir alle möglichen Kombinationen dieser Zeichen liefert, also beispielsweise

DAELN
DALEN
DANEL
DALNE
...
NADEL
NALDE
NADLE
...
LADEN
...

und so weiter. Ist zwar nicht so ganz effizient, aber das ist jetzt erst einmal egal. Das Problem dabei ist halt, dass die Anzahl der Zeichen flexibel sein muss. Ich will es in Visual Basic realisieren, aber ich bräuchte ja eigentlich erst einmal nur eine Idee. Ich würde es für 3 Zeichen so machen:


for a=1 to len(string)
for b=1 to len(string)
if b<>a then
for c=1 to len(string)
if c<>b and c<>a then
'String zusammenbauen
end if
next
end if
next
next

Naja, ein wenig unübersichtlich ;-)... ich hoffe, das Problem ist klar. Nur wie mache ich das jetzt mit variabler Stringlänge? Ich hab schon an Rekursion gedacht, aber noch keine konkrete Vorstellung, wie ich es realisieren könnte.

Vielen Dank im Voraus :)!

[FireBird2002]

Rekursion hört sich ganz gut an. Hier meine Idee: Jeder Buchstabe muß irgendwann an den Stringanfang. Die restlichen Möglichkeiten sind Kombinationen des Reslichen Zeichenvorrats. Du mußt nur eine Funktion finden/schreiben, die dir einen Buchstaben eines Strings löscht. Du mußt das ganze dann in einem Array of Strings speichern. Die Größe des Arrays kannst du vorher berechnen(Kombinatorik: Ich weiß dass es damit geht, aber nicht wie). Du mußt nur die Indizes richtig verteilen.

[Jan Krüger]

Rekursion wird wahrscheinlich lahm, denn es gibt in diesem Fall 120 verschiedene Kombinationen.
Sollte mir irgendwas schlaues (konstruktiveres) einfallen, werd ich mich nochmal melden. ;)

(bei 6 Buchstaben » 720
7 » 5040
8 » 40320
... wird recht viel ;))

[Shooter]

Jo, dass das lahm sein wird, das war mir von vornerein klar. Mir geht es erst einmal um das zugrunde liegende Prinzip... wie könnte ich so etwas eigentlich überhaupt realisieren im Detail?

@FireBird2002:
Die Größe des Arrays könnte ich schon berechnen, das wäre n! (sprich: "n Fakultät", n steht für die Anzahl der Zeichen), also bei 3 Zeichen 3*2*1=6 oder bei 5 Zeichen 5*4*3*2*1=120. Nur wie ich so etwas zusammenbaue, du sagtest etwas von einer Funktion zum Entfernen von Zeichen oder so, das ist mir noch unklar.

[FireBird2002]

@Shooter:

Du mußt das Zeichen, dass du als erstes Zeichen ausgewählt hast, aus dem String entfernen. Dann kannst du den Reststring wieder an die (rekursuve) Funktion übergeben. Die einzelnen Zeichen würde ich in eine Klasse speichern, die das entsprechende Zeichn rauslöscht und die nachfolgenden Zeichen aufrücken läßt. Ich habe auch keine Idee wie sich das programmiertechnisch realisieren läßt.
Ich versuchs mal formal (So ne Mischung aus allen Programiersprachen):


Klasse String
...

String[] kombination(String bla) {
String temp;
String temp2[],ret[];
if StringLänge(bla)>0 {
for i=0 to StringLänge(bla) {
temp=bla.NimmBuchstabe(i);
temp2[i]=kombination(bla.loescheBuchstabe(i));
for j=0 to StringLänge(bla)-1 {
ret[j] =temp2[j]+temp;
}
}
}
return ret[];
}

Ich weiß nicht ganz genau obs so funktionieren könnte...

[Shooter]

Danke FireBird, ich habs jetzt so gelöst:


Private Sub FindeKombinationen(ByRef strTextPrefix As String, _
ByRef strSrcText As String)

Dim i As Integer, intLenSrc As Integer, Foo As Integer

DoEvents

intLenSrc = Len(strSrcText)
If intLenSrc < 2 Then
Debug.Print strTextPrefix & strSrcText
Else
For i = 1 To intLenSrc
Call FindeKombinationen( _
strTextPrefix + Mid$(strSrcText, i, 1), _
Left$(strSrcText, i - 1) + Right$(strSrcText, intLenSrc - i))
Next i
End If
End Sub


Vielen Dank noch einmal an alle!