Algoritmo per O (1) selezione casuale ponderata con rimozione

Question

Sto cercando un algoritmo di selezione casuale ponderato con caratteristiche simili a alias method, eccetto dove gli elementi vengono rimossi dopo che sono stati selezionati.

Ad esempio, ho una borsa che produce:

• Un rosso di marmo il 70% del tempo.
• Un marmo verde il 10% delle volte.
• E un marmo blu il 20% delle volte.

Assaggio la borsa e prendo un marmo rosso. Ora il rosso è stato rimosso, quindi immagino che la borsa ora produca:

• Un marmo verde il 33% delle volte.
• Un marmo blu il 66% delle volte.

Credo che si possa precomporre un albero di ogni possibile tabella di probabilità, in modo che il campione sia ancora O(1). Sono gli algoritmi più intelligenti per la selezione ponderata a tempo costante con la rimozione?

Answer 1

In realtà, sembra che abbia erroneamente letto la domanda. Non ero a conoscenza del metodo di alias e la risposta seguente non è un algoritmo analogo. Lascerò qui la mia risposta perché è ancora informativa.

---

Io non sono a conoscenza di un O (1) algoritmo, ma è facile da fare in log (N) di ricerca e accedere aggiornamento (N). Questo può essere migliorato con un algoritmo più specifico.

Metti i tuoi elementi in un Fenwick tree, con le loro probabilità come valori. Anche quando si cambiano gli elementi si tiene traccia della probabilità cumulativa totale.

Ora possiamo fare di meglio che rimuovere solo gli elementi! Possiamo modificare arbitrariamente la probabilità degli oggetti, ma impostare la probabilità di un oggetto a 0 equivale a rimuoverlo. È quindi possibile interrogare nel log (N) la probabilità cumulativa dello n elemento th. Questo logicamente si estende ad un log (N) ricerca binaria del primo elemento con una probabilità cumulativa maggiore di p.

Ora, per effettuare la selezione casuale ponderata, generiamo un numero p tra 0 e P dove P è la probabilità cumulativa totale. Quindi eseguiamo la ricerca binaria sopra descritta per trovare e selezionare il primo elemento con probabilità cumulativa maggiore di p.

---

ho migliorato di quanto sopra, perché l'utilizzo di un albero Fenwick è facile fare un log (N) Ricerca per il primo elemento con probality cumulativa maggiore o uguale a p. Posso suggerire caldamente di leggere this explanation of Fenwick trees.

In poche parole, per trovare l'elemento, eseguire una ricerca binaria regolare sull'albero di Fenwick come si farebbe su qualsiasi altro albero, con l'eccezione che si mantiene una somma cumulativa corrente (a partire da 0).Ogni volta che si sceglie il bambino della mano destra nella ricerca binaria, incrementare la somma cumulativa corrente per il valore del nodo corrente. Quindi, quando si confronta il valore del nodo corrente con la somma cumulativa che stiamo cercando, aggiungere il valore del nodo corrente alla somma finora prima di comparare.