Shuffle eines Strings

[backdraft]

Hallo,

ich habe ein Problem, was ich nicht wirklich zu lösen weis.

Ich habe einen String der 36 Zeichen lang ist. In dem String ist jedes Zeichen nur einmal vorhanden (A-Z, 0-9).

Ich möchte, dass die Reihenfolge der Ziffern jetzt gemischt wird, und zwar über einen Parameter.
Wichtig ist, dass wenn ich z.B. Parameter 1 übergebe, das sich immer die gleiche Reihenfolge bekomme.
Das gleiche für Parameter 2,3 bis X (maximale Anzahl an Kombinationen).

Hat jemand eine Idee für so einen Algo?

Oliver

[cruiser]

Dir ist klar, dass es da etwa 3,72*10^41 Möglichkeiten gibt? Ein Unsigned Int64 hat nur einen Maximalwert von etwa 1,844*10^19 .

Wenn du also nicht zusätlich noch eine BigInt Implementierung verwenden wilst, musst du dir allein für den parameter etwas einfallen lassen.

[Namenloser]

Ist die Frage, ob die Kombination eindeutig sein muss, sodass man auf den Urstring rückschließen kann, oder ob das ganze wie eine Art Hash funktionieren soll.

[backdraft]

Zitat:

Zitat von cruiser

Dir ist klar, dass es da etwa 3,72*10^41 Möglichkeiten gibt? Ein Unsigned Int64 hat nur einen Maximalwert von etwa 1,844*10^19 .

Wenn du also nicht zusätlich noch eine BigInt Implementierung verwenden wilst, musst du dir allein für den parameter etwas einfallen lassen.

Jo ist mir klar :-) Ich will ja auch nicht alle Möglichkeiten haben, sondern 2^32 Kombinationen (Integer) haben, die aber immer ungleich einer anderen ist.

Zitat:

Zitat von NamenLozer

Ist die Frage, ob die Kombination eindeutig sein muss, sodass man auf den Urstring rückschließen kann, oder ob das ganze wie eine Art Hash funktionieren soll.

Einen Rückschluss brauche ich nicht. Wichtig ist nur, dass die Ziffern nicht doppelt sind, und keine andere dazubekommen sind. Also wirklich nur mischen.

[sx2008]

Du brauchtst einen eigenen Zufallsgenerator. Er nuss nicht besonders gut sein. Es reicht ein Generator nach der linearen Konkruenzmethode.

Delphi-Quellcode:

var
  g_seed:integer;

function fastrand:integer;  // "geklaut" von [url]http://softwarecommunity.intel.com/articles/eng/2978.htm[/url]
begin
   g_seed := 214013*g_seed+2531011;
   result := (g_seed shr 16) and $7FFF;
end;

Warum nicht Random() benützen ? Weil Borland den random() Generator ändern könnte.
Ausserdem wäre das nicht portabel. Keine Ahnung, ob FreePascal die gleiche random() Funkt
benützt als Borland.

Und dann einfach 36 Mal die Zeichen vertauschen:

Delphi-Quellcode:

  g_Seed := deinIntParameter;
  for i:=1 to 36 do
  begin
    // swapChar vertauscht zwei Chars - deine Hausaufgabe
    SwapChar(s[i], s[fastrand mod 36 +]);
  end;

[backdraft]

Hi, danke!

Geht perfekt. Aber mich würde interessieren, ob die Zahle 214013 + 2531011 Zufall sind, oder genau das machen, was ich will, nämlich keine doppelte Kombi erzeugen.

[sx2008]

Zitat:

Zitat von backdraft

Aber mich würde interessieren, ob die Zahle 214013 + 2531011 Zufall sind, oder genau das machen, was ich will, nämlich keine doppelte Kombi erzeugen.

Die Zahlen sind speziell ausgesucht, um eine möglichst lange Periodenlänge des Generators zu erhalten.
Wenn's dich interessiert, dann kannst du ja mal einen Test fahren:

Delphi-Quellcode:

var rcounter: array[0..32767] of Word;

for i := 1 to 32768*10 do
begin
  Inc(rcounter[fastrand]);
end;

Wenn du das array graphisch auswertest, sollte überall *ungefähr* 10 drinstehen.

[grenzgaenger]

Deine Anzahl von Kombinantionen ist jedoch auf die Periodenlänge des Zufallsgenerators beschränkt.