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

Hi,
ich möchte ein paar zufällige Zahlen haben, die sich unterscheiden.
z.B. 10 (ganze) Zahlen zwischen 0 und 99. Dabei möchte ich 10 verschiedene haben.
Gibt es da eine fertige c++ Funktion?
Es gibt ja std::random_shuffle, die shuffelt aber alle 100 Zahlen. Wenn ich nun aber 1000 aus 1.000.000 haben möchte ist das viel Arbeit umsonst.

Gibt es da eine effektivere Möglichkeit?

Schlangenmensch

Schau mal hier: http://www.cplusplus.com/reference/random/

Du musst nur zusätzlich ausschließen, dass eine Zahl doppelt vorkommt.

SeppJ

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

Das Verfahren skaliert gut für alle möglichen Wertemengen und alle möglichen Anzahlen an zu ziehenden Werten.

Tipp: Wenn die Liste als Vector implementiert wird, geschieht das Löschen des gezogenen Wertes am effizientesten, indem man ihn mit dem Wert am Ende des Vectors überschreibt und dann den Wert am Ende abschneidet. Schließlich ist die Reihenfolge der Werte innerhalb des Vectors egal.

Schlangenmensch schrieb:

Schau mal hier: http://www.cplusplus.com/reference/random/

Du musst nur zusätzlich ausschließen, dass eine Zahl doppelt vorkommt.

Meinst du, quasi dann testen, ob ich sie bereits habe? Das wollte ich ja gerade nicht.
Aber ich schaue mir den link mal genauer an, danke.

SeppJ schrieb:

Gibt es nicht fertig, aber ist leicht selber zu programmieren:
1. Liste mit den Werten, aus denen gezogen werden soll machen

Das geht eben nicht. Wenn ich warum auch immer 10 Elemente aus 100 Millionen haben möchte, müsste ich einen Vektor mit 100 Millionen Elementen machen. Das wollte ich eben vermeiden.

SeppJ

Vorhin waren es noch bis zu einer Million Zahlen, da wäre mein Verfahren noch gut. Ein einziges Verfahren, das für wirklich beliebige m und n perfekt skaliert, wirst du nicht finden. Schlangenmenschs Methode ist gut für kleine m und beliebig große n, aber schlecht wenn m groß wird oder wenn m nahe an n ist. Mein Verfahren ist gut für beliebige m, solange n nicht gigantisch ist. Für gigantische m und n könnte man, wenn m nahe n, ein umgekehrtes Verfahren machen, indem man mit Schlangenmensch Methode die Zahlen ermittelt, die nicht gezogen wurden. Für große m (zu groß für Schlangenmensch Methode) und gigantische n (zu groß für meine Methode) fällt mir spontan nichts ein, was da noch wirklich gut ist. Irgendwann wird das Problem eben ziemlich schwer.

Caligulaminus

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

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

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.

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.

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.

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.

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?