Pseudo-willekeurig algoritme voor het selecteren van semi-willekeurig item in een array

Ik heb een eenvoudige array (of stel deze in als u dat wilt) van gehele getallen, laten we dit X noemen. Ik heb ook een andere array W die het "gewicht" van elementen in array X opslaat. Het "gewicht" geeft aan hoe waarschijnlijk het n-de element moet zijn geselecteerd zijn. Nu heb ik een methode (algoritme) nodig om (willekeurig) een element uit array/set X te selecteren op basis van het 'gewicht' dat in array W is gedefinieerd.

Bijvoorbeeld, als mijn W er zo uitziet:     W [0] = 2;     W [1] = 4;     W [2] = 6;

dat betekent dat de kans om een ​​N-de item uit array X te selecteren, is:     X [0] = 16,6%     X [1] = 33,3%     X [2] = 50%

dus methode get_pseudorandom_item (X) zou het tweede item ongeveer de helft van alle keren moeten retourneren.

Alle ideeën of suggesties hoe dit te implementeren (in elke programmeertaal) worden zeer op prijs gesteld. Bedankt.

1

4 antwoord

  1. Generate an array P with the partial sums of the weights, i.e.

    (P0 = W0), (P1 = W0 + W1), ..., (Pn = W0 + W1 + ... + Wn)

    (you can do that within W, actually, if you don't need the weights afterwards).

  2. Generate a random number r in [0, Pn) where Pn denotes the last such sum (i.e. the sum of all weights).

  3. Find the index k of the smallest (first) partial sum larger than the number you generated:

    Pk > r  ∧  ∀ a < k: Pa < r

  4. Use that index to select your actual element: Xk

7
toegevoegd
Als snelheid belangrijk is, kunt u in stap 3 binair zoeken gebruiken, omdat de array niet-aflopend is en dus gesorteerd.
toegevoegd de auteur svick, de bron

Laten we aannemen dat de getallen in X [] optellen tot 1,0. Dus X [2] zou 0.5000 zijn.

Je kiest je nummer en voegt het toe totdat je 'geen kans meer hebt'.

Hier is een Java-voorbeeld:

double rand = random.nextDouble();
double sofar = 0.0;

for(int i = 0; i < X.length; x++) {
    if(sofar + X[i] > rand) return W[i];
    sofar += X[i];
}
throw new IllegalStateException("Numbers add up to less than 1");
1
toegevoegd

Voor elk objecttype x [i] Waarbij y het gewicht is. Voeg y-elementen toe in een array van het type x [i].

Selecteer vervolgens willekeurig uit deze array.

Als u uw voorbeeld neemt, heeft u 2 W [0], 4 W [1] en 6 W [2] in de verzameling waaruit u willekeurig een item kiest dat van het type 0, 1 of 2 is.

1
toegevoegd
Dit is leuk als je veel ruimte (geheugen) hebt en de tafel met gewichten herhaaldelijk zult gebruiken. In deze oplossing hoeft u geen gewichtentabel te doorzoeken.
toegevoegd de auteur Heath Hunnicutt, de bron
Akkoord, het is niet het meest efficiënte algoritme.
toegevoegd de auteur Sid Malani, de bron

Het eerste dat me te binnen schiet is geen erg mooie oplossing, maar ik zal het toch delen!

U kunt een andere array maken (bijvoorbeeld met 100 gehele getallen). Elk geheel getal vertegenwoordigt de index in W . Op basis van het gegeven percentage kunt u die array met de gehele getallen vullen.

Dus als je X [0] = 25% X hebt [1] = 25% X [2] = 50% De array zou 25 1's, 25 2's en 50 3's hebben

Vervolgens kunt u een pseudo-willekeurige index van die array selecteren en de geretourneerde index gebruiken om het object op te halen in W .

Zoals ik al zei, het is lelijk, maar het zou lukken :)

0
toegevoegd