"ABCD" in allen möglichen Kombinationen

[3_of_8]

Ich würde mal sagen, ein solcher Algorithmus sollte schon generisch sein.

Und im allgemeinen kann man sagen: Schneller als von Hagen gehts ned.

@Cöster: Ja, ich weiß. Das hab ich ja gleich gesagt. Aber die Aussage, ein String könne nur 255 Zeichen lang sein, stimmt auch nicht. Jedenfalls nur für ShortStrings, also diese alten Dinger.

[Cöster]

Zitat:

Zitat von 3_of_8

Aber die Aussage, ein String könne nur 255 Zeichen lang sein, stimmt auch nicht.

Hab ich das gesagt?

Zitat:

Zitat von Cöster

Das Wort kann aus bis zu 255 Zeichen bestehen.

Code:

if Ein String = Das Wort then
  ich hab gelogen
else
  hab ich auch nie gesagt

@ Dino: Bei mir ist meine Variante ca. doppelt so schnell wie deine. :mrgreen: Aber bei 7 Zeichen ist die Geschwindigkeit ja sowieso nicht so wichtig.

Fliegt der Code von Hagen hier auch irgendwo im Forum rum? Würd mich mal interessieren. Können normal Sterbliche den überhaupt verstehen?

[negaH]

also, schneller gehts immer, es gibt immer andere Programmierer die noch mehr drauf haben als man selber drauf hat. Ich verwehre mich also hiermit ausdrücklich das meine Codes die schnellsten sein müssen. Allerdings bin ich schon ein Freak der den Ehrgeiz hat den bestmöglichen Algorithmus zu finden, und dabei natürlich ne Menge lernen möchte. Das impliziert aber eben nicht das meine Codes die schnellsten sein müssen. Auf Alzaimar, Olliver oder NicoDE und auf die viele Anderen hier würde die gleiche Aussage auch zutreffen.

http://www.delphipraxis.net/internal...561&highlight=

Es findet sich hier in der DP aber auch eine Lösung von Alzaimar die ich persönlich als sehr elegant empfinde und die mindestens genauso effizient sein muß wie die meinige. Einfach mal suchen.

Zitat:

Können normal Sterbliche den überhaupt verstehen?

Nöö, natürlich nicht, ich bin ja anscheinend unsterblich. Nur merke ich die letzten 2 Wochen davon nichts, sonst würde ich nicht auf Grund meiner derzeitgen Bronchitis nicht ständig am Husten sein (Raucher) ;) Klar wirst du ihn verstehen du musst dich halt nur intensiv damit beschäftigen wollen.

Gruß Hagen

[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

Delphi-Quellcode:

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.

[-lx-]

Hallo.


Nach langem informieren, überlegen und ein wneig lunzen auf andere Codes hab ich nun etwas zu stande gebarcht bzw. zu "Papier".

Ich will euch dne Code nicht vorenthalten, jedoch läuft er noch nicht einbahnfrei. Sprich: Er gibt was aus aber noch das falsche.

Da mir die Lösung erst um 12 Uhr (24 Uhr Ortszeit) eingefallen ist, hab ich nun nicht mehr die Kraft alles durhc zu spinnen und zu überlegen wo der Haken liegt.

Wer mag kann sich diesen NOCH FEHLERHAFTEN Code anschaun und vll. auch mal kurze Hilfestellung geben ;)

Delphi-Quellcode:

procedure Permutation(n: Integer; const Text: String) ;
    var i: Integer ;
        CopyText, Neu: String ;
        begin
          CopyText:= Text ;
          For i:= n To length(CopyText) Do
              begin
                If length(CopyText) >= 1 Then
                    begin
                      showmessage('hallo');
                      Neu:= Neu + CopyText[i] ;
                      Delete(CopyText, i, 1) ;
                    end
                Else
                    begin
                      Neu:= Neu + CopyText[i] ;
                      Memo1.Lines.Add(Neu) ;
                    end;
                If n < length(CopyText) Then Permutation(n+1, Text) ;
                Memo1.Lines.Add(Neu) ;
              end;

        end;

Gute Nacht alle miteinder :)


//Edit: Ich merke, da ist noch einiges an Verbesserung nötig ...