m unterschiedliche zufällig Zahlen aus 0 bis n ziehen, c++ funktion?

[Caligulaminus]

Oder einfach so lange Zufallszahlen in ein (unordered_)set stecken, bis .size() == m ?

[RandomName]

Caligulaminus schrieb:

Oder einfach so lange Zufallszahlen in ein (unordered_)set stecken, bis .size() == m ?

Das enspricht von der Laufzeit her Schlangenmensch's Vorschlag oder?
Edit: Scheint zumindest im Average case besser zu sein.

Wie groß m und n sind kann ich nicht allgemein sagen. Während der Laufzeit können sie sehr unterschiedlich oder sehr ähnlich sein. m hat aber einen Maximalwert, n ist irgedendwo dazwischen n>=m^1 und n<=m^4, meist aber n~= m^2

Eine Fallunterscheidung, je nachdem wie groß sie sind ist auch doof.
Und wäre halt gut wenn man vorher sagen kann, wie lang es dauert. Schlangenmensch's Vorschlag kann ja, wenn man unglaubliches Pech hat Ewigkeiten dauern.

[SeppJ]

RandomName schrieb:

Caligulaminus schrieb:

Oder einfach so lange Zufallszahlen in ein (unordered_)set stecken, bis .size() == m ?

Das enspricht von der Laufzeit her Schlangenmensch's Vorschlag oder?
Edit: Scheint zumindest im Average case besser zu sein.

Das ist nur eine andere Implementierung, Schlangenmensch hat schließlich nicht gesagt, wie genau die Prüfung stattfinden soll. Für sehr kleine m (sagen wir mal < 100) ist vermutlich eine lineare Suche ganz ok, für größere Mengen dann eben Divide&Conquer wie beim Set. Oder man kann ja auch ein unordered_set heran ziehen, das sollte immer ganz ok sein.

Eine Fallunterscheidung, je nachdem wie groß sie sind ist auch doof.

Wieso? Ist doch clever, je nach Bedarf einen besser geeigneten Algorithmus zu wählen.

Und wäre halt gut wenn man vorher sagen kann, wie lang es dauert. Schlangenmensch's Vorschlag kann ja, wenn man unglaubliches Pech hat Ewigkeiten dauern.

Wenn absolut perfekte Vorhersagekraft nötig ist, ist Schlangenmenschs Methode nicht geeignet, aber ich behaupte mal, dass du dir das Leben selber unnötig schwer machst, wenn du diese verlangst. Ist es wirklich relevant, wenn Schlangenmenschs Methode in 0.000001% aller Fälle länger braucht als erwartet? Meine Methode ist übrigens von der Laufzeit her perfekt vorhersagbar.

[camper]

RandomName schrieb:

Das enspricht von der Laufzeit her Schlangenmensch's Vorschlag oder?
Edit: Scheint zumindest im Average case besser zu sein.

Kommt darauf, wie du feststellst, ob eine Zahl bereits gezogen wurde.

Eine Modifikation vermeidet wiederholtes Ziehen:
N=Anzahl Zahlen (0 ... N-1)
M=Anzahl zu ziehen
m=Anzahl bereits gezogen

1. Ziehe Zahl x 0 ... (N-1-m)
2. Beginnend bei der kleinsten bereits gezogenen Zahl: erhöhe x um 1 für jede gezogene Zahl y, mit y <= x

Schritt 2 könnte man für hinreichend kleine M einfach per sortierter Liste handhaben => O(M*M); für größere M könnte ein balancierter Suchbaum, der sich die Anzahl der (direkten und indirekten) Kindknoten merkt, verwendet werden => O(M*log(M)) mit rel. großem k

[RandomName]

SeppJ schrieb:

Meine Methode ist übrigens von der Laufzeit her perfekt vorhersagbar.

Aber verbraucht viel Platz. Aber ich glaub ich werde es trotzdem nehmen, 10 Millionen Integer sind auch nur 40Megabyte. Copmuter soll sich mal nicht so anstellen.
Hhmm, aber in einen Durchlauf wird das nicht nur einmal gemacht. Bei 10Millionen müsste er ca. 100Mio Werte initialisieren, dann wärn wir schon bei 400MB für z.B 10k Zufallswerte, macht 40KB pro Zahl.

[RandomName]

camper schrieb:

Eine Modifikation vermeidet wiederholtes Ziehen:
N=Anzahl Zahlen (0 ... N-1)
M=Anzahl zu ziehen
m=Anzahl bereits gezogen

1. Ziehe Zahl x 0 ... (N-1-m)
2. Beginnend bei der kleinsten bereits gezogenen Zahl: erhöhe x um 1 für jede gezogene Zahl y, mit y <= x

Das ist nicht mehr 100% uniform zufall aber schaut nicht schlecht aus, danke.

[SeppJ]

RandomName schrieb:

SeppJ schrieb:

Meine Methode ist übrigens von der Laufzeit her perfekt vorhersagbar.

Aber verbraucht viel Platz. Aber ich glaub ich werde es trotzdem nehmen, 10 Millionen Integer sind auch nur 40Megabyte. Copmuter soll sich mal nicht so anstellen.
Hhmm, aber in einen Durchlauf wird das nicht nur einmal gemacht. Bei 10Millionen müsste er ca. 100Mio Werte initialisieren, dann wärn wir schon bei 400MB für z.B 10k Zufallswerte, macht 40KB pro Zahl.

Kommt auf die Details an. Wenn es nicht parallel geschieht und die Grundmenge immer gleich sein sollte, kann man die alte Liste weiter verwenden. Man muss die Zahlen ja nicht wirklich löschen, es reicht schließlich, die gezogenen Zahlen ans Ende zu sortieren und dann die ober Schranke für die Zufallszahl um eins zu verringern.

Bei 10k Werten würde ich einfach die Methode von Schlangenmensch benutzen, wenn Speicherplatz wirklich ein Problem ist.
~~
Noch eine andere Idee, die ausnutzt, dass deine Wertemenge natürliche Zahlen sind: Man nehme die Methode von Schlangenmensch. Wenn man eine Zahl zieht, die es schon gab, dann zieht man keine komplett neue Zahl, sondern sucht (in beide Richtungen) nach der nächsten ungezogenen Zahl und nimmt stattdessen diese. Wenn mich nicht alles täuscht, sollte dies die Verteilung der gezogenen Zahlen nicht beeinflussen,~~ aber man vermeidet so die Gefahr, dass der Algorithmus gegen Ende sehr lange sucht, wenn er 999,999 Zahlen aus 1,000,000 ziehen soll.

edit: Habe campers Vorschlag nicht gesehen, der so ähnlich ist wie meine Modifikation von Schlangenmenschs Methode. campers Vorschlag ist besser als meine Modifikation. Ich sehe gerade nicht, wieso campers Methode die Verteilung stören sollte.
edit2: Meine Methode war doch nicht gleichverteilt. Ich unterstütze campers Vorschlag.

[camper]

RandomName schrieb:

camper schrieb:

Eine Modifikation vermeidet wiederholtes Ziehen:
N=Anzahl Zahlen (0 ... N-1)
M=Anzahl zu ziehen
m=Anzahl bereits gezogen

1. Ziehe Zahl x 0 ... (N-1-m)
2. Beginnend bei der kleinsten bereits gezogenen Zahl: erhöhe x um 1 für jede gezogene Zahl y, mit y <= x

Das ist nicht mehr 100% uniform zufall aber schaut nicht schlecht aus, danke.

Erklärung?

[scrontch]

RandomName schrieb:

SeppJ schrieb:

Meine Methode ist übrigens von der Laufzeit her perfekt vorhersagbar.

Aber verbraucht viel Platz. Aber ich glaub ich werde es trotzdem nehmen, 10 Millionen Integer sind auch nur 40Megabyte. Copmuter soll sich mal nicht so anstellen.
Hhmm, aber in einen Durchlauf wird das nicht nur einmal gemacht. Bei 10Millionen müsste er ca. 100Mio Werte initialisieren, dann wärn wir schon bei 400MB für z.B 10k Zufallswerte, macht 40KB pro Zahl.

Was wird nicht nur einmal gemacht? Wenn Du öfter von vorne anfangen willst, dann häng einfach die vorher gezogenen Zahlen wieder an den Vektor hinten dran. Das entspricht dem zurücklegen in die Urne.

[camper]

SeppJ schrieb:

Noch eine andere Idee, die ausnutzt, dass deine Wertemenge natürliche Zahlen sind: Man nehme die Methode von Schlangenmensch. Wenn man eine Zahl zieht, die es schon gab, dann zieht man keine komplett neue Zahl, sondern sucht (in beide Richtungen) nach der nächsten ungezogenen Zahl und nimmt stattdessen diese. Wenn mich nicht alles täuscht, sollte dies die Verteilung der gezogenen Zahlen nicht beeinflussen, aber man vermeidet so die Gefahr, dass der Algorithmus gegen Ende sehr lange sucht, wenn er 999,999 Zahlen aus 1,000,000 ziehen soll.

Bei dieser Methode besteht für eine Zahl, die zu einer bereits gezogenen Zahl, benachbart liegt, eine größere Wahrscheinlichkeit, gezogen zu werden, als für eine Zahl, deren Nachfolger und Vorgänger noch nicht gezogen wurden.

[scrontch]

Inspiriert durch camper (dessen Methode ich aber gerade nicht blicke ):
Oder arbeite einfach nur mit einem einzigen Vektor [0..N-1], bei dem sowohl die Urne [0..N-1-m] als auch das was rausgezogen wurde drin ist [N-m..N-1].

mit V[N-1-m].

Und dann m++

Wenn Du hier fertig bist und neu anfangen willst brauchst du hier gar nichts weiter tun! Einfach wieder mit m=0 von vorne anfangen.

[RandomName]

camper schrieb:

RandomName schrieb:

camper schrieb:

Eine Modifikation vermeidet wiederholtes Ziehen:
N=Anzahl Zahlen (0 ... N-1)
M=Anzahl zu ziehen
m=Anzahl bereits gezogen

1. Ziehe Zahl x 0 ... (N-1-m)
2. Beginnend bei der kleinsten bereits gezogenen Zahl: erhöhe x um 1 für jede gezogene Zahl y, mit y <= x

Das ist nicht mehr 100% uniform zufall aber schaut nicht schlecht aus, danke.

Erklärung?

Tut mir Leid ich hab y '>=' x gelesen. Mit <= sollte es passen. Danke.

[RandomName]

Liste wiederverwenden gestaltet sich schwierig, da n sich ändert.
Muss also z.b. sicherstellen, dass keine Zahl in der Liste größer als das aktuelle n ist und auch das jedes zahl zwischen 0 und n vorhanden ist.

[camper]

scrontch schrieb:

Inspiriert durch camper (dessen Methode ich aber gerade nicht blicke ):
Oder arbeite einfach nur mit einem einzigen Vektor [0..N-1], bei dem sowohl die Urne [0..N-1-m] als auch das was rausgezogen wurde drin ist [N-m..N-1].

mit V[N-1-m].

Und dann m++

Wenn Du hier fertig bist und neu anfangen willst brauchst du hier gar nichts weiter tun! Einfach wieder mit m=0 von vorne anfangen.

Das ist SeppJs ursprüngliche Variante.

Hier meine in richtigem C++

template <typename URBG>
vector<int> get_random_sequence(URBG& g, int N, int M) {
    assert( M <= N );
    vector<int> result, sorted;
    for ( int m = 0; m < M; ++m ) {
        int x = uniform_int_distribution( 0, N - 1 - m )( g );
        auto it = sorted.begin();
        for ( ; it != sorted.end(); ++it ) {
            if ( y > x )
                break;
            ++x;
        }
        sorted.insert( it, x );
        result.push_back( x );
    }
}

Die Baum-Variante ist ein bisschen komplexer.

[RandomName]

Danke für den Code, ich hatte es nach dem Lesefehler zwar schon kapiert aber kann ja nicht schaden

Hat das eigenlich auch einen Namen oder selbst ausgedacht?

[camper]

RandomName schrieb:

Hat das eigenlich auch einen Namen oder selbst ausgedacht?

Ja.

[AnotherRandomOne]

Zieh einfach 10 mal Zahlen zwischen 0 und 9 und addiere zur n. Zahl n*10

[Fricky667]

SeppJ schrieb:

Gibt es nicht fertig, aber ist leicht selber zu programmieren:
1. Liste mit den Werten, aus denen gezogen werden soll machen
2. Zufälligen Wert daraus ziehen
3. Gezogenen Wert aus der Liste entfernen
4. Schritte 2. und 3. wiederholen bis die gewünschte Anzahl Werte gezogen wurde

Geht noch einen Tick einfacher.
1. Array mit gültigen Werten befüllen.
2. random-shuffle auf diesem Array ausführen.
3. die ersten n Werte nehmen und fertig.

[SeppJ]

Fricky667 schrieb:

SeppJ schrieb:

Gibt es nicht fertig, aber ist leicht selber zu programmieren:
1. Liste mit den Werten, aus denen gezogen werden soll machen
2. Zufälligen Wert daraus ziehen
3. Gezogenen Wert aus der Liste entfernen
4. Schritte 2. und 3. wiederholen bis die gewünschte Anzahl Werte gezogen wurde

Geht noch einen Tick einfacher.
1. Array mit gültigen Werten befüllen.
2. random-shuffle auf diesem Array ausführen.
3. die ersten n Werte nehmen und fertig.

Wieder mal Quatsch. Dadurch hast du viel mehr Rechenaufwand, ohne jeden Zugewinn.

[Fricky667]

SeppJ schrieb:

Dadurch hast du viel mehr Rechenaufwand, ohne jeden Zugewinn.

Meinst du wirklich? Die STL hat doch eine Random-Shuffle-Funktion. Ist die wirklich so schlecht (aus Benutzersicht wie auch Processor-Cycles betreffend)?