Pseudo-zufällige Permutation mit 128 Bit Seed

Question

Ich bin auf der Suche nach ein paar Funktionen, die den Index eines Vektors auf effiziente Weise per Seeding mit 128-Bit-Schlüssel permieren. Optimierung ist für mich kritisch, da ich die gleiche Operation mehrmals mache.

Kann jemand eine C/C++ - Open-Source-Bibliothek vorschlagen, in der 128-Bit-Seeding verfügbar ist und eine Funktion wie Permute (Seed, Range (Min, Max), Sample_Size) unterstützt?

Zum Beispiel; Wenn die Funktion permute (1, [0,10], 10) das Ergebnis als 3 6 7 2 4 9 8 1 0 5 ergibt, dann sollte permute (1, [0,10], 5) 3 6 7 2 ergeben 4.

Parameter min, max und sample_size sind dynamische Variablen. Es ändert sich bei jeder Iteration.

Answer 1

Keine Notwendigkeit für eine Bibliothek (! So ist es eigentlich beim Thema)

std::shuffle gibt Ihnen die Permutation; Es dauert ein UniformRandomBitGenerator wie std::mt19937. std::mt19937::seed() nimmt eine Sequenz, so können Sie es 128 Bits des Ausgangszustands füttern. Und einen Teilbereich zu nehmen ist natürlich trivial.

Answer 2

können Sie Fisher–Yates_shuffle verwenden:

// Fisher–Yates_shuffle 
std::vector<int> 
FisherYatesShuffle(std::size_t size, std::size_t max_size, std::mt19937& gen) 
{ 
    assert(size < max_size); 
    std::vector<int> res(size); 

    for (std::size_t i = 0; i != max_size; ++i) { 
     std::uniform_int_distribution<> dis(0, i); 
     std::size_t j = dis(gen); 
     if (j < res.size()) { 
      if (i < res.size()) { 
       res[i] = res[j]; 
      } 
      res[j] = i; 
     } 
    } 
    return res; 
} 

Live example