Array Shuffle mit Seed

  • C#
  • .NET (FX) 1.0–2.0

Es gibt 22 Antworten in diesem Thema. Der letzte Beitrag () ist von Mokki.

    Array Shuffle mit Seed

    Hey,

    Ich möchte mir folgendes programmieren, weiß jedoch nicht wie ich es anstellen soll :
    Eine Funktion die ein byte[] returned und ein byte[] sowie einen integer als Parameter akzeptiert, also ca so :

    C#-Quellcode

    1. ​private static byte[] SeedShuffle(byte[] input, int seed)
    2. {
    3. // black magic
    4. return input;
    5. }



    Die Funktion soll das Input-Array shufflen, allerdings den Integer als eine Art "Seed" verwenden, d.h. das geshufflte
    byte[] hat jedes mal die gleiche Reihenfolge, sofern Input-Array und der Seed-Integer gleich sind.
    Wenn der Seed sich ändert, soll ein anderes geshuffltes Ergebnis rauskommen.
    Mir ist klar das es Überschneidungen geben kann, - wenn mein Input-Array bspw nur aus zwei Elementen besteht, gibt es auch nur zwei
    möglich Anordnungen, - d.h. es gibt mehrere Seed-Integer die das gleiche "geshuffelte" Array ergeben.
    Das ist jedoch nicht weiter schlimm, - bei größeren Arrays sollte es viele Variationen geben...
    Hat jemand eine Idee wich ich das am besten realisiere?
    C# Developer
    Learning C++

    Rikudo schrieb:

    realisiere
    es einfach mit diesem Ansatz:

    VB.NET-Quellcode

    1. Dim seed = CInt(NumericUpDown1.Value)
    2. Dim rnd = New Random(seed)
    3. ListBox1.Items.Clear()
    4. For i = 1 To 10
    5. ListBox1.Items.Add(rnd.Next(100))
    6. Next
    Oder hab ich das Problem falsch verstanden?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RodFromGermany“ ()

    Hi
    verwende eine Random-Instanz mit Seed und vertausche je zwei Werte des Eingangsarrays. Auch hier gilt übrigens, lieber zusätzlich eine Methode anzubieten, die das ursprüngliche Array verwendet, Klonen kann der Aufrufer immer noch. Wenn das Array weggeworfen wird, vergeht wertvolle Zeit, bzw. die Funktionalität wird dadurch eingeschränkt.

    C#-Quellcode

    1. static void Shuffle<T>(T[] input, int seed)
    2. {
    3. var rnd = new Random(seed);
    4. for(int i = 0; i < input.Length; i++)
    5. {
    6. //item an index i mit beliebigem Item vertauschen
    7. var v = input[i];
    8. int m = rnd.Next(0, input.Length);
    9. input[i] = input[m];
    10. input[m] = v;
    11. }
    12. }


    Wenn du für zwei verschiedene Arrays gleicher Länge bei gleichem Seed verschiedene Werte möchtest, würde ich dir empfehlen, den Seed über den Hashcode nochmal neu zu berechnen:

    C#-Quellcode

    1. static void Shuffle<T>(T[] input, int seed)
    2. {
    3. var rnd = new Random(seed);
    4. //Ausgehend vom seed die Hashcodes ver-x-odern. Bei identischen Arrays ist der generierte Wert identisch, bei verschiedenen Arrays i.A. nicht
    5. seed = input.Aggregate(seed, (v, o) => v ^ o.GetHashCode());
    6. for(int i = 0; i < input.Length; i++)
    7. {
    8. //item an index i mit beliebigem Item vertauschen
    9. var v = input[i];
    10. int m = rnd.Next(0, input.Length);
    11. input[i] = input[m];
    12. input[m] = v;
    13. }
    14. }


    Der Aufruf für die von dir gewünschte Funktionalität wäre dann halt entsprechend

    C#-Quellcode

    1. ​private static byte[] SeedShuffle(byte[] input, int seed)
    2. {
    3. var cr = (byte[])input.Clone();
    4. Shuffle(cr, seed);
    5. return cr;
    6. }


    Viele Grüße
    ~blaze~
    Als Ergänzung vielleicht:

    MSDN schrieb:

    Providing an identical seed value to different Random objects causes each instance to produce identical sequences of random numbers.

    MS macht aber keine Aussagen darüber, dass der gleiche seed bei unterschiedlichen Plattformen/Versionen das gleiche Ergebnis produziert. Es kann also gut sein, dass unter einer anderen Konfiguration (32/64bit, Mono, andere .Net-Version, ...), eine andere Sequenz produziert wird.
    Wenn das relevant ist, solltest du auf eine andere Implementation zurückgreifen.
    @3daycliff, - das ist auf jeden Fall gut zu wissen denn ich überlege mir gerade wie ich das
    geshufflte Ergebnis mithilfe des Seed werts wieder in die Ausgangsreihenfolge "zurückshuffeln" kann.
    D.h. in dem seed muss die Information gespeichert werden wie die bytes geshufflt wurden, so das
    man später mithilfe des seeds auch wieder die Elemente zurück-shuffeln kann.
    Das Problem ist das ich nicht weiß wie ich diese Informationen in einem Integer codieren soll, - wenn das
    Inputarray sehr groß ist ist das analog (durch bspw bits set/unset) nicht mehr möglich, - d.h. man
    bräuchte einem mathematischen Ansatz der bei einer beliebigen Größe x des Input arrays immer noch funktioniert.
    Hat das jemand ein paar Ideen die er gerne Teilen möchte? :D
    C# Developer
    Learning C++

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Rikudo“ ()

    Rikudo schrieb:

    zurückshuffeln
    ohne es probiert zu haben:
    Mit dem selben seed-value eine äquivalente Routine schreiben, wo Source und Target vertauscht sind, wie Encrypr und Decrypt.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Wie ist Dein

    Rikudo schrieb:

    Shuffle
    -Algorithmus?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Rikudo schrieb:

    code von blaze
    Das geht. Idee:
    Array von hinten nach vorn, Zufallszahlen von hinten nach vorn, da musst Du natürlich am Anfang n Zufallszahlen auslesen, in ein Array packen und die von hinten nach vorn anwenden.
    Feddich. :thumbup:
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Hi
    wäre sehr hässlich. Du musst dann nämlich die Indices rotieren. Für kleine Datenpackete kein Problem, für große unperformant. Besser wäre, eine Funktion für die Permutation zu verwenden und die Umkehrungsfunktion ausgehend vom gleichen Seed zu bestimmen. Da würd' ich dann aber einfach ein bewährtes Verfahren verwenden.
    Random verwendet Pseudozufallszahlen, du hast sowieso maximal 2^32 Möglichkeiten, über eine Analyse der Vorkommen oder dergleichen könnte man vmtl. auch den Algorithmus knacken, wenn man genügend Datenlänge hat.

    Viele Grüße
    ~blaze~

    ~blaze~ schrieb:

    Da würd' ich dann aber einfach ein bewährtes Verfahren verwenden.


    An was hast du da genau gedacht?
    Den Fisher-Yates Algo?
    Der ist jedoch afaik nicht wirklich reversibel, - zumindest nicht mit einem einzigen Integer als Seed.
    C# Developer
    Learning C++
    Ich hab grad damit nen bisle rumexperimentiert. Die Gegenfunktion von @~blaze~ ist:

    C#-Quellcode

    1. static void shuffleback<T>(T[] input, int seed)
    2. {
    3. var rnd = new Random(seed);
    4. //Ausgehend vom seed die Hashcodes ver-x-odern. Bei identischen Arrays ist der generierte Wert identisch, bei verschiedenen Arrays i.A. nicht
    5. seed = input.Aggregate(seed, (v, o) => v ^ o.GetHashCode());
    6. int[] x = new int[input.Length];
    7. for (int i = 0; i < input.Length; i++)
    8. {
    9. x[i] = rnd.Next(0, input.Length);
    10. }
    11. for (int i = input.Length - 1; i > -1; i--)
    12. {
    13. //item an index i mit beliebigem Item vertauschen
    14. var v = input[i];
    15. int m = x[i];
    16. input[i] = input[m];
    17. input[m] = v;
    18. }
    19. }

    Zumindest hat es bei mir in mehreren Testläufen funktioniert.
    Der doppelte Schleifenaufruf ist aber bei großen Array ein hoher zeitlicher Aufwand, habe aber leider keine Gegenfunktion zu Random.Next gefunden.
    ​Smartnotr - ein intelligentes Notizprogramm
    zum Thread

    Rikudo schrieb:

    von Shuffln nicht von encrypten reden
    Das ist in diesem Kontext doch identisch, Du suchst einen Algorithmus, der Zahlen iwie behandelt und den komplementären Algorithmus, der die behandelten Zahlen "enthandelt".
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Rikudo schrieb:

    Random.Next()
    Random.Before().
    Das hatten wir schon.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!