Gewichtete Zufallszahlen

Aktualisierte Antwort auf eine alte Frage. Sie können dies in C++ 11 ganz einfach mit der std :: lib tun:

#include <iostream>
#include <random>
#include <iterator>
#include <ctime>
#include <type_traits>
#include <cassert>

int main()
{
    // Set up distribution
    double interval[] = {1,   2,   3,   4};
    double weights[] =  {  .90, .56, .04};
    std::piecewise_constant_distribution<> dist(std::begin(interval),
                                                std::end(interval),
                                                std::begin(weights));
    // Choose generator
    std::mt19937 gen(std::time(0));  // seed as wanted
    // Demonstrate with N randomly generated numbers
    const unsigned N = 1000000;
    // Collect number of times each random number is generated
    double avg[std::extent<decltype(weights)>::value] = {0};
    for (unsigned i = 0; i < N; ++i)
    {
        // Generate random number using gen, distributed according to dist
        unsigned r = static_cast<unsigned>(dist(gen));
        // Sanity check
        assert(interval[0] <= r && r <= *(std::end(interval)-2));
        // Save r for statistical test of distribution
        avg[r - 1]++;
    }
    // Compute averages for distribution
    for (double* i = std::begin(avg); i < std::end(avg); ++i)
        *i /= N;
    // Display distribution
    for (unsigned i = 1; i <= std::extent<decltype(avg)>::value; ++i)
        std::cout << "avg[" << i << "] = " << avg[i-1] << '\n';
}

Ausgabe auf meinem System:

avg[1] = 0.600115
avg[2] = 0.373341
avg[3] = 0.026544

Beachten Sie, dass der größte Teil des obigen Codes nur zum Anzeigen und Analysieren der Ausgabe bestimmt ist. Die eigentliche Generierung besteht nur aus wenigen Codezeilen. Die Ausgabe zeigt, dass die angeforderten "Wahrscheinlichkeiten" erhalten wurden. Sie müssen die angeforderte Ausgabe durch 1,5 dividieren, da dies die Summe der Anforderungen ist.

Wenn sich Ihre Gewichte langsamer ändern als gezeichnet, wird C++ 11 discrete_distribution wird am einfachsten sein:

#include <random>
#include <vector>
std::vector<double> weights{90,56,4};
std::discrete_distribution<int> dist(std::begin(weights), std::end(weights));
std::mt19937 gen;
gen.seed(time(0));//if you want different results from different runs
int N = 100000;
std::vector<int> samples(N);
for(auto & i: samples)
    i = dist(gen);
//do something with your samples...

Beachten Sie jedoch, dass die c ++ 11 discrete_distribution berechnet alle kumulierten Summen bei der Initialisierung. Normalerweise möchten Sie das, weil es die Abtastzeit einmalig beschleunigt O(N) Kosten. Bei einer sich schnell ändernden Verteilung entstehen jedoch hohe Berechnungs nd Speicherkosten) Beispiel: Wenn die Gewichtung angibt, wie viele Elemente vorhanden sind, und Sie jedes Mal, wenn Sie eines zeichnen, entfernen, möchten Sie wahrscheinlich einen benutzerdefinierten Algorithmus.

Wills Antwort --- (https://stackoverflow.com/a/1761646/837451 vermeidet diesen Overhead, zeichnet sich jedoch langsamer ab als C++ 11, da keine binäre Suche verwendet werden kann.

Um dies zu überprüfen, können Sie die entsprechenden Zeilen (/usr/include/c++/5/bits/random.tcc auf meiner Ubuntu 16.04 + GCC 5.3 Installation):

  template<typename _IntType>
    void
    discrete_distribution<_IntType>::param_type::
    _M_initialize()
    {
      if (_M_prob.size() < 2)
        {
          _M_prob.clear();
          return;
        }

      const double __sum = std::accumulate(_M_prob.begin(),
                                           _M_prob.end(), 0.0);
      // Now normalize the probabilites.
      __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
                            __sum);
      // Accumulate partial sums.
      _M_cp.reserve(_M_prob.size());
      std::partial_sum(_M_prob.begin(), _M_prob.end(),
                       std::back_inserter(_M_cp));
      // Make sure the last cumulative probability is one.
      _M_cp[_M_cp.size() - 1] = 1.0;
    }

Was ich mache, wenn ich Zahlen gewichten muss, ist die Verwendung einer Zufallszahl für das Gewicht.

Zum Beispiel: Ich muss Zufallszahlen von 1 bis 3 mit den folgenden Gewichten generieren:

• 10% einer Zufallszahl könnten 1 sein
• 30% einer Zufallszahl könnten 2 sein
• 60% einer Zufallszahl könnten 3 sein

Dann benutze ich:

weight = Rand() % 10;

switch( weight ) {

    case 0:
        randomNumber = 1;
        break;
    case 1:
    case 2:
    case 3:
        randomNumber = 2;
        break;
    case 4:
    case 5:
    case 6:
    case 7:
    case 8:
    case 9:
        randomNumber = 3;
        break;
}

Dabei hat es zufällig 10% der Wahrscheinlichkeiten, 1, 30%, 2 und 60%, 3 zu sein.

Sie können damit nach Ihren Wünschen spielen.

Hoffe ich konnte dir helfen, Viel Glück!

Bauen Sie einen Beutel (oder std :: vector) mit allen Gegenständen, die kommissioniert werden können.
Stellen Sie sicher, dass die Anzahl der Artikel proportional zu Ihrer Gewichtung ist.

Beispiel:

• 1 60%
• 2 35%
• 3 5%

So haben Sie eine Tasche mit 100 Artikeln mit 60 1, 35 2 und 5 3.
Sortiere nun den Beutel zufällig (std :: random_shuffle)

Entnehmen Sie nacheinander Elemente aus dem Beutel, bis dieser leer ist.
Einmal leer, re-randomisiere den Beutel und beginne erneut.

Wählen Sie eine Zufallszahl für [0,1], die der Standardoperator () für ein Boost-RNG sein sollte. Wählen Sie den Artikel mit kumulativer Wahrscheinlichkeitsdichtefunktion> = diese Zahl:

template <class It,class P>
It choose_p(It begin,It end,P const& p)
{
    if (begin==end) return end;
    double sum=0.;
    for (It i=begin;i!=end;++i)
        sum+=p(*i);
    double choice=sum*random01();
    for (It i=begin;;) {
        choice -= p(*i);
        It r=i;
        ++i;
        if (choice<0 || i==end) return r;
    }
    return begin; //unreachable
}

Dabei gibt random01 () ein double> = 0 und <1 zurück. Beachten Sie, dass für das oben Gesagte nicht die Wahrscheinlichkeit 1 erforderlich ist. es normalisiert sie für dich.

p ist nur eine Funktion, die einem Element in der Sammlung eine Wahrscheinlichkeit zuweist [begin, end). Sie können es weglassen (oder eine Identität verwenden), wenn Sie nur eine Folge von Wahrscheinlichkeiten haben.