String "mischen"

[FriFra]

Ich suche eine möglichst einfache Möglichkeit einen beliebig langen String mit einem Zufallsgenerator komplett "durcheinander zu Würfeln"

z.B.: dasisteintest -> stiestndeista

Aber ich will nicht immer z.B. Zeichen 2 an Position 8 oder Zeichen 4 an Position 1, sondern eine wirklich zufällige Anordnung!

[anku]

versuch es mal so:

Delphi-Quellcode:

var sOrginal, sKopie, sEndproduckt: String;
    i, Zufall: Integer;

begin
 randomize; // am besten bei programmstart ausführen, da sonst of gleiche "zufalls" ergebnisse kommen
 for i:= 1 to length( sOrginal) do
  sKopie[i]:= Chr(255); // mit platzhalter füllen
 for i:= l to length( sOrginal) do
   while true do //solange loopen bis freie stelle gefunden
   begin
     Zufall:= random( Length( sOrginal))+1; //Zufallstelle
     if sKopie[ Zufall] = Chr(255) then begin 
       sKopie[Zufall]:= sOrginal[i]; 
       break; // aus der while schleife springen
     end;
   end;
end;

oder so ähnlich..

mfg

[neolithos]

Delphi-Quellcode:

function MixString(sOrg : String) : String;
...
randomize;
Result := '';
while Length(sOrg) > 0 do
  begin
    i := Random(Length(sOrg) + 1);
    Result := Result + sOrg[I];
    Delete(sOrg, I, 1);
  end;

Achtung: nicht getestet, sondern aus dem Ärmel geschüttelt

[Robert Marquardt]

Beide Sourcen gefallen mir nicht.
Die effizienteste Idee ist es, zwei Buchstaben des Strings zufaellig auszuwaehlen und zu vertauschen. Das macht man ein paar hundert Mal und der String ist zuverlaessig verwuerfelt. Man kann das noch adaptieren und x Mal Laenge des Strings oft tauschen.

[daniel-volk]

So, ich hab mal diesen Code geschrieben und auch getestet:

Delphi-Quellcode:

function TForm1.MixString(mixstr : string):string;
var i, x1, x2 : longword;
    rem1, rem2 : Char;
begin
  Case length(mixstr)>0 of
  true : begin
         Screen.Cursor := crHourGlass;
         randomize;
         x2 := Random(length(mixstr))+1;
         for i := 1 to 1000*length(mixstr)
         do begin
              x1 := Random(length(mixstr))+1;
              rem1 := Char(mixstr[x1]);
              rem2 := Char(mixstr[x2]);
              mixstr[x1] := rem2;
              mixstr[x2] := rem1;
              x2 := x1;
            end;
         result := mixstr;
         Screen.Cursor := crDefault;
         end;
  false : result := '';
  end;
end;

Die Problematik bei einem solchen Code ist immer, dass zwei Zufallszahlen zugleich generiert werden müssen. Da die dann aber fast immer gleich ausfallen, muss man den Rechner zwischendurch etwas beschäftigen. Ich hab das jetzt so gemacht, dass der Rechner immer eine Zahl der vorherigen "Ziehung" speichert. Auf diese Weise wird das Mischen überhaupt erst möglich!
Trotzdem kann ich dir nicht garantieren, dass es nicht auch bei diesem Code vorkommt, dass gleiche Zufallszahlen generiert werden, weil der Code, der zwischenzeitlich ausgeführt wird, dennoch sehr gering ist.

Soll es noch zufälliger werden, dann musst du dich mal nach dem Thema "Pseudozufallszahlen" erkundigen. Das führt dann aber zwangsläufig zu komplizierten Algorithmen und langen Generationszeiten. Zudem muss der Nutzer meistens die Maus bewegen.

MfG.

[daniel-volk]

Noch etwas zu Thema:
Der Code von anku verursachte bei mir eine Zugriffsverletzung und der Code von neolithos "vergisst" einfach Zeichen, sodass der String hinterher ein paar Zeichen kürzer sein kann oder gleich '' ist.
Bei meinem Code habe ich mal die Zufälligkeit getestet.
Dafür habe ich mir ein kleines Prog gebaut, in das ich meinen Originalstring eingegeben habe. Das Prog hat diesen nun vermischt und das Ergebnis schließlich mit dem Original verglichen. Das ganze wurde so lange wiederholt, bis der String mit dem Original übereinstimmte.

Hier die Ergebnisse:
String mit 3 Zeichen:
Berechneter Sollwert (maximale Möglichkeiten = 3 Fakultät): 6 Versuche
Getesteter Durchnitt: 184 Versuche (Durchschnitt aus 10 Durchläufen)

String mit 5 Zeichen:
Sollwert: 120 Versuche
Durchschnitt: 1688,1 Versuche

Fazit: Das Mischen mit dem Code geht sehr schnell und eigentlich auch ganz gut.
Dennoch wiederholt sich ein String nur alle 10 bis 20 mal seltener, als es normalerweise der Fall sein müsste! Hierfür kann es zwei Gründe geben:
1) Der Code scheut sich aus irgendeinem Grund davor, den String wieder in die Ursprungsform zu bringen. Diese Theorie wäre belegt, wenn man den Versuch so gestalten würde, dass als Ergebnis nicht wieder der Ausgangsstring entstehen soll, sondern ein schon gemischter String und dann die Zufallswerte eine bessere Form annehmen würden.
2) Ein und derselbe Zufallswert kehrt 10-20 mal wieder. Dies halteich auf jeden Fall für wahrscheinlicher. Zur genaueren Untersuchung müsste man einfach mal die Zufallswerte loggen.

@ Robert Marquardt:
Du siehst also: Wirklich effizient ist das auch nicht. Für den 0815-User aber auf jeden Fall ausreichend.

MfG.

PS: Sorry für die lange Erklärung, hab aber nun mal Physik- und Mathe-LK.

[anku]

ok, dann jetzt mal ohne fehler..

Delphi-Quellcode:

        sOrginal:= 'abcde';        
        sKopie:='';
        for i:= 1 to length( sOrginal) do
        begin
                Zufall:= random( Length( sOrginal))+1;
                Insert( sOrginal[i], sKopie, Zufall);
        end;

und neolithos:

        sOrginal:= 'abcde';
        sKopie:='';
        while length( sOrginal)>0 do
        begin
                 Zufall:= Random( Length( sOrginal))+1;
                 sKopie:= sKopie + sOrginal[Zufall];
                 Delete( sOrginal, Zufall, 1);
        end;

wobei neolithos beispiel besser abschneidet. ~120 versuche bis das orginal und der mix übereinstimmen. im vergleich zu daniel-volks algo immer noch schwach, aber es sollte trotzdem ausreichen. in einem punkt sind sie diesem aber überlegen, der string darf ~1000mal länger bis ein integer overflow eintritt *g

nichts für ungut

mfg

[F.W.]

Ich habe mal ein bisschen herum probiert und habe da was gefunden, was ich für einfach und doch sehr Wirkungsvoll finde!

Delphi-Quellcode:

function TForm1.MixString(Enter: String): String;
var
 S: String;
 R: Integer;
 SL: TStringList;
begin
 SL := TStringList.Create;
  try
(******Buchstaben einsetzen********)
 S := '';
 for R := 1 to Length(Enter) do
     SL.Add(Enter[R]);
(******Buchstaben mischen**********)
 Randomize;
 while SL.Count > 0 do begin
       R := Random(SL.Count);
       Insert(SL[R], S, Length(S)+1);
       SL.Delete(R);
 end;
 Result := S;
(**********************************)
  finally
 SL.Free;
  end;
end;

Das ganze funktioniert also mit einer Stringlist, in die alle Buchstaben eingetragen werden, danach wird einer rausgepickt und zum Ergebnis hinzugefügt und in der StringList gelöscht, so kann er nicht nocheinmal genommen werden.

Es ist ein bisschen spät, aber vielleicht nützt es ja noch jemandem was!