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

SG1

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

hustbaer

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.