n einzigartige zufallszahlen



  • hat da einer eine idee, die nicht in einem Loop steckenbleiben kann 😕

    vllt sowas wie array shuffle aber das wäre schon sehr ineffizient 😞



  • Also ich habe Zahlen von 0..x und brauche daraus dann Zufallszahlen. Die müssen auch nicht besonders zufällig sein 😉 😞



  • nimm die ersten N Zahlen der (zufällig!) permutierten Zahlen X.

    Bsp.: X={1,2,3,....,10}
    N=3

    perm(X)={4,1,10,...}
    und jetzt die ersten N=3 Einträge nehmen, also {4,1,10}.

    Wie du Zahlenfolgen permutierst findest du sicher im Internet.
    Ganz primitiv könnte das etwa so aussehen, dabei gehst du über alle Einträge von X und tauscht jeden Eintrag mit einem zufälligen, anderen Eintrag:

    Pseudocode:

    X={...}; % initialisiere deine Zahlenfolge
    for(i=0;i<X.size();++i)
    {
      swap(X[i],X[getRandomNumber()%X.size()]); // tausche Eintrag i mit zufälligem Eintrag 
    }
    
    result=X[1...3]; // nimm erste drei Einträge
    


  • Der Pseudocode erzeugt aber keine gleichverteilten Permutationen. Siehe https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#Implementation_errors

    Und wenn man den Shuffle schon so explizit hinschreibt, kann man auch i<N als Abbruchbedingung nehmen, nicht i<X.size().



  • SG1 schrieb:

    Der Pseudocode erzeugt aber keine gleichverteilten Permutationen. Siehe https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#Implementation_errors

    Und wenn man den Shuffle schon so explizit hinschreibt, kann man auch i<N als Abbruchbedingung nehmen, nicht i<X.size().

    wo waren gleichverteilte Zufallszahlen gefragt? Kein Zweifel - diese Art der Permutation ist die erste die mir in den Sinn gekommen ist, da gibts zweifelsohne bessere.
    Aber betreffend der Aufgabe denke ich ist das ok, Zitat: "Die müssen auch nicht besonders zufällig sein "



  • Hab da schon ein Fisher–Yates shuffle in der lib. Aber, dann muss ich ja ein Array von allen Zahlen erstellen.. Naja, werd es dann so machen 😞



  • bambi schrieb:

    Hab da schon ein Fisher–Yates shuffle in der lib. Aber, dann muss ich ja ein Array von allen Zahlen erstellen.. Naja, werd es dann so machen 😞

    von wievielen Zahlen sprechen wir denn?
    Selbst bei 16bit=2byte Ganzzahlen hast du dann nur 2*2^16byte = 2^17byte ~ 131kByte. Und ich nehme mal stark an, dass bei euch nur eine Teilmenge davon gefragt ist, z.B. Zahlen aus dem Intervall 1 bis 1000.

    Also kein Grund zur Sorge solange du einen halbwegs modernen PC dein eigen nennst 😉



  • Wie gross sind denn X und N inetwa?
    Wenn N << X, dann wäre es vermutlich schneller das Array zu virtualisieren.
    D.h. du speicherst nur die Einträge die eine Zahl != Index enthalten. Denn der Fisher–Yates muss ja nicht vollständig durchlaufen - du brauchst ja nur die ersten N Zahlen. Also können auch nur 2*N Einträge mit Zahl != Index sein, also musst du nicht viele Zahlen speichern. Initialisieren musst du auch "nix", denn zu Anfang ist ja jeder Eintrag Zahl == Index.

    Bei grossen X und kleinen N wird sich das sicherlich gut auszahlen.

    In C++ würde ich dazu ne std::unordered_map vorschlagen - was man in C da nimmt wenn man es nicht selbst schreiben will ... keine Ahnung. So lange N klein genug bleibt natürlich einfach ein Array.


Anmelden zum Antworten