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

temi

Vielleicht lässt sich ja daraus etwas machen?

http://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/

Kommt vermutlich darauf an, wie die Qualität der Zufallszahlen sein soll.

Leider verstehe ich (noch) nicht, wie campers Vorschlag funktioniert, aber immer wieder interessant hier mitzulesen.

camper

temi schrieb:

Leider verstehe ich (noch) nicht, wie campers Vorschlag funktioniert, aber immer wieder interessant hier mitzulesen.

Im Prinzip ist das auch nur eine Variantion von SeppJs Algorithmus, mit dem Unterschied, dass nicht eine Liste der noch ziehbaren Zahlen geführt wird, sondern eine, die die gezogenen Zahlen enthält, also praktisch eine Liste der Lücken in SeppJs Liste. Nimmt man noch SeppJs Optimierungsvorschlag hinzu, könnte man einfach eine map benutzen, die bereits gezogenen Zahlen auf solche abbildet, die nicht mehr durch den Primäroutput des Generators erreicht werden können:

template <typename URBG>
vector<int> get_random_sequence(URBG& g, int N, int M) {
    assert( M <= N );
    vector<int> result;
    unordered_map<int, int> q;
    for ( int m = 0; m < M; ++m ) {
        int x = uniform_int_distribution( 0, N - 1 - m )( g );
        auto last = q.find( N - 1 - m );
        auto map_to = last == q.end() ? N - 1 - m : last->second;
        auto [it, insert_success] = q.try_emplace( x, map_to );
        if ( !insert_success ) {
            x = it->second;
            it->second = map_to;
        }
        if ( last != q.end() {
            q.erase( last );
        }
        result.push_back( x );
    }
    return result;
}