Cum se implementează un amestec ponderat

Am scris recent un cod pe care l-am considerat foarte ineficient, dar din moment ce include doar câteva valori, l-am acceptat. Cu toate acestea, sunt încă interesat de un algoritm mai bun pentru următoarele:

este ales

  1. O listă de X obiecte, fiecăruia dintre ele i se atribuie o „greutate”
  2. Rezumați greutățile
  3. Generați un număr aleator de la 0 la sumă
  4. Iterează prin obiecte, scăzând greutatea lor din sumă până când suma nu este pozitivă
  5. Eliminați obiectul din listă, apoi adăugați-l la sfârșitul noii liste

Elementele 2, 4 și 5 toate necesită n timp, deci este un algoritm O (n ^ 2).

Poate fi îmbunătățit?

Ca exemplu de amestecare ponderată, este mai probabil ca un element să fie în față cu o greutate mai mare.

Exemplu (voi genera numere aleatorii pentru ao face real):

6 obiecte cu greutate 6,5,4,3,2,1; Suma este 21

Am ales 19: 19-6-5-4-3-2 = -1 deci 2 intră pe prima poziție, greutățile sunt acum 6,5,4,3,1; Suma este 19

Am ales 16 16-6-5-4-3 = -2:, deci 3 merge pe poziția a doua, greutățile sunt acum 6,5,4,1; Suma este 16

Am ales 3: 3-6 = -3 deci 6 merge pe poziția a treia, greutățile sunt acum 5,4,1; Suma este 10

Am ales 8:, 8-5-4 = -1 deci 4 merge pe a patra poziție, greutățile sunt acum 5.1; Suma este 6

Am ales 5:, 5-5 = 0 deci 5 merge pe poziția a cincea, greutățile sunt acum la 1; Suma este 1

Am ales 1:, 1-1 = 0 așa că 1 merge pe ultima poziție, nu mai am greutate, termin

Acest lucru poate fi implementat în O (n log (n)) folosind un arbore.

Mai întâi creați structura arborelui păstrând în fiecare nod suma cumulativă a tuturor nodurilor descendente din dreapta și din stânga fiecărui nod.

Pentru a testa un element, eșantionați recursiv din nodul rădăcină, utilizând sumele care rulează pentru a decide dacă returnați nodul curent, un nod stâng sau un nod drept. Ori de câte ori eșantionați un nod, setați greutatea acestuia la zero și actualizați și nodurile părinte.

Iată implementarea mea în Python:

weigthed_shuffle este un generator, astfel încât să puteți testa cele mai bune elemente în mod eficient. Dacă doriți să amestecați întreaga matrice, doar iterați peste generator până la epuizare (utilizând funcția listă).

ACTUALIZAȚI:

Eșantionarea ponderată aleatorie (2005; Efraimidis, Spirakis) oferă un algoritm foarte elegant în acest sens. Implementarea este foarte simplă și rulează și în O (n log (n)):

EDITAȚI | ×: Acest răspuns nu interpretează ponderile așa cum era de așteptat. Cu alte cuvinte, un articol de greutate 2 nu este de două ori mai probabil să fie prim decât un articol de greutate 1.

O modalitate de a amesteca o listă este de a atribui numere aleatorii fiecărui element din listă și de a le sorta după acele numere. Putem extinde această idee, trebuie doar să alegeți numere aleatoare ponderate. De exemplu, puteți utiliza random () * weight. Opțiuni diferite vor produce distribuții diferite.