Hogyan lehet megvalósítani a súlyozott keverést

Nemrég írtam egy kódot, amely szerintem nagyon hatástalan volt, de mivel csak néhány értéket tartalmazott, elfogadtam. Mindazonáltal továbbra is érdekel egy jobb algoritmus a következőkre:

1. X objektum listája, mindegyikhez "súly" tartozik
2. Foglalja össze a súlyokat
3. Generáljon véletlen számot 0-tól az összegig
4. Iteráljuk az objektumokat, kivonva azok súlyát az összegből, amíg az összeg nem pozitív
5. Távolítsa el az objektumot a listáról, majd adja hozzá az új lista végéhez

A 2., 4. és 5. elem mindegyike n időt vesz igénybe, tehát O (n ^ 2) algoritmusról van szó.

Javítható-e rajta?

A súlyozott keverés példájaként egy elem nagyobb valószínűséggel elöl helyezkedik el, nagyobb tömeggel.

Példa (véletlenszerű számokat generálok, hogy valódiak legyenek):

6 tárgy 6,5,4,3,2,1 súlyú; Az összeg 21

A 19: 19-6-5-4-3-2 = -1 értéket választottam, így 2 az első helyre kerül, a súlyok most 6,5,4,3,1; Az összeg 19

16-ot választottam 16-6-5-4-3 = -2:, tehát 3 megy a második pozícióba, a súlyok most 6,5,4,1; Az összeg 16

A 3: 3-6 = -3 értéket választottam, így a 6 a harmadik helyre kerül, a súlyok most 5,4,1; Az összeg 10

A 8-at választottam:, 8-5-4 = -1, így 4 a negyedik pozícióba kerül, a súlyok most 5,1; Az összeg 6

Az 5-öt választottam:, 5-5 = 0, így az 5 az ötödik pozícióba kerül, a súlyok most 1-nél vannak; Az összeg 1

Az 1-et választottam:, 1-1 = 0, így 1 az utolsó pozícióba kerül, nincs több súlyom, befejezem

Ez megvalósítható O-ban (n log (n)) egy fa segítségével.

Először hozza létre a fát úgy, hogy minden csomópontban megtartja az összes leszálló csomópont összesített összegét az egyes csomópontoktól jobbra és balra.

Elem mintavételéhez rekurzív módon vegyen mintát a gyökércsomópontból, a futó összegek segítségével döntse el, hogy az aktuális, a bal vagy a jobb csomópontot adja-e vissza. Amikor csomópontot vesz mintába, állítsa nullára annak súlyát, és frissítse a szülő csomópontokat is.

Itt van a megvalósításom a Pythonban:

A weigthed_shuffle egy generátor, így hatékonyan mintázhatja k a legjobb elemeket. Ha a teljes tömböt el akarja keverni, csak iteráljon a generátoron a kimerülésig (a lista funkcióval).

FRISSÍTÉS:

A súlyozott véletlenszerű mintavétel (2005; Efraimidis, Spirakis) erre egy nagyon elegáns algoritmust biztosít. A megvalósítás nagyon egyszerű, és O-ban is fut (n log (n)):

SZERKESZTÉS: Ez a válasz nem a várt módon értelmezi a súlyokat. Más szavakkal, a 2. súlyú tétel nem kétszer olyan valószínű, hogy elsődleges, mint az 1. súlyú tétel.

A lista keverésének egyik módja az, hogy véletlenszerű számokat rendel a lista minden eleméhez, és ezeket a számok szerint rendezi. Kiterjeszthetjük ezt az elképzelést, csak súlyozott véletlenszerű számokat választhatunk. Például használhatja a random () * weight értéket. A különböző választási lehetőségek különböző eloszlásokat eredményeznek.

---