"ABCD" in allen möglichen Kombinationen

[alzaimar]

Um mal meinen Senf dazuzugeben, hier die kurze Version. Ich find sie auch elegant, vor allen Dingen, weil Sie als Abfallprodukt eines anderen Problems enstanden ist. Davor habe ich mich mit Inversen und Graycodes beschäftigt, um Permutationen zu erzeugen, aber das ist ein anderes Thema.

Delphi-Quellcode:

Type
  TCharSet = Set Of Char;

Procedure TForm1.Permutation(Const aString, aResult : String; anIndex : Integer; aUsedChars : TCharSet);
Var
  i : Integer;

Begin
  For i:=1 to Length (aString) do
    if not (aString[i] in aUsedChars) then
      If anIndex = Length (aString) Then
        Memo1.lines.add(aResult+aString[i])
      Else
        Permutation (aString, aResult + aString[i], anIndex + 1, aUsedChars + [aString[i]]);
End;

Aufruf mit
Permutation (edit1.Text, '',1, []) Der Algorithmus versagt allerdings, wenn ein in einem Wort ein Zeichen doppelt vorkommt, aber das sind dann klassisch gesehen keine Permutationen, denn die basieren ja auf einer Menge von Zeichen. Und in einer Menge gibts keine doppelten Elemente (gott-sei-dank).

Ein Wort noch zu der Performance. Bei diesem Minimalalgorithmus habe ich bewusst darauf verzichtet, den Flaschenhals "Stringkonkatenation" wegzuoptimieren. Das Problem ist ja der rekursive Aufruf, in dem eine Konkatenation steht.
Ein winziger Test bestätigt allerdings, das der Geschwindigkeitszuwachs marginal ist. Erst bei Wortlängen>7 ist überhaupt eine Verzögerung spürbar und dann geht der Performancegewinn schon gegen 0.

Viel wichtiger ist der Container, der die Permutationen aufnehmen soll. Eine Stringliste wie hier (womöglich noch als visuelles Element) ist sowieso die größte Bremse. Besser ist ein dynamisches Array, das vorher auf die korrekte Länge (N!) gesetzt wird.

Ich kann mir allerdings keinen Fall vorstellen, bei dem man zunächst alle Permutationen erzeugt, um sie dann -wie auch immer- zu verarbeiten. Normalerweise lässt sich ein solches Problem viel eleganter (und damit meist auch performanter) lösen.