Come implementare un shuffle ponderato

Questo può essere implementato in O(n log(n)) usando un albero.

Per prima cosa, crea l'albero, mantenendo in ogni nodo la somma cumulativa di tutti i nodi discendenti a destra e a sinistra di ogni nodo.

Per campionare un elemento, campionare in modo ricorsivo dal nodo radice, utilizzando le somme cumulative per decidere se restituire il nodo corrente, un nodo da sinistra o un nodo da destra. Ogni volta che assumi un nodo, imposta il peso a zero e aggiorna anche i nodi parent.

Questa è la mia implementazione in Python:

import random

def weigthed_shuffle(items, weights):
    if len(items) != len(weights):
        raise ValueError("Unequal lengths")

    n = len(items)
    nodes = [None for _ in range(n)]

    def left_index(i):
        return 2 * i + 1

    def right_index(i):
        return 2 * i + 2

    def total_weight(i=0):
        if i >= n:
            return 0
        this_weigth = weights[i]
        if this_weigth <= 0:
            raise ValueError("Weigth can't be zero or negative")
        left_weigth = total_weight(left_index(i))
        right_weigth = total_weight(right_index(i))
        nodes[i] = [this_weigth, left_weigth, right_weigth]
        return this_weigth + left_weigth + right_weigth

    def sample(i=0):
        this_w, left_w, right_w = nodes[i]
        total = this_w + left_w + right_w
        r = total * random.random()
        if r < this_w:
            nodes[i][0] = 0
            return i
        elif r < this_w + left_w:
            chosen = sample(left_index(i))
            nodes[i][1] -= weights[chosen]
            return chosen
        else:
            chosen = sample(right_index(i))
            nodes[i][2] -= weights[chosen]
            return chosen

    total_weight() # build nodes tree

    return (items[sample()] for _ in range(n - 1))

Utilizzo:

In [2]: items = list(range(10))
   ...: weights = list(range(10, 0, -1))
   ...:

In [3]: for _ in range(10):
   ...:     print(list(weigthed_shuffle(items, weights)))
   ...:
[5, 0, 8, 6, 7, 2, 3, 1, 4]
[1, 2, 5, 7, 3, 6, 9, 0, 4]
[1, 0, 2, 6, 8, 3, 7, 5, 4]
[4, 6, 8, 1, 2, 0, 3, 9, 7]
[3, 5, 1, 0, 4, 7, 2, 6, 8]
[3, 7, 1, 2, 0, 5, 6, 4, 8]
[1, 4, 8, 2, 6, 3, 0, 9, 5]
[3, 5, 0, 4, 2, 6, 1, 8, 9]
[6, 3, 5, 0, 1, 2, 4, 8, 7]
[4, 1, 2, 0, 3, 8, 6, 5, 7]

weigthed_shuffle è un generatore, quindi puoi campionare in modo efficiente gli articoli k in cima. Se vuoi mescolare l'intero array, basta scorrere il generatore fino all'esaurimento (usando la funzione list ).

UPDATE:

Weighted Random Sampling (2005; Efraimidis, Spirakis) fornisce un algoritmo molto elegante per Questo. L'implementazione è semplicissima e viene eseguita anche in O(n log(n)) :

def weigthed_shuffle(items, weights):
    order = sorted(range(len(items)), key=lambda i: -random.random() ** (1.0 / weights[i]))
    return [items[i] for i in order]

EDIT: questa risposta non interpreta i pesi nel modo che ci si aspetterebbe. Cioè un oggetto con peso 2 non ha il doppio di probabilità di essere il primo di peso 1.

Un modo per mescolare un elenco è assegnare numeri casuali a ciascun elemento nell'elenco e ordinare questi numeri. Possiamo estendere questa idea, dobbiamo solo selezionare numeri casuali ponderati. Ad esempio, potresti utilizzare random() * weight . Diverse scelte produrranno diverse distribuzioni.

In qualcosa come Python, questo dovrebbe essere semplice come:

items.sort(key = lambda item: random.random() * item.weight)

Fai attenzione a non valutare i tasti più di una volta, poiché finiranno con valori diversi.

Innanzitutto, lascia che il peso di un dato elemento nell'elenco da ordinare sia costante. Non cambierà tra le iterazioni. Se lo fa, allora ... beh, questo è un problema più grande.

Per illustrazione, utilizziamo un mazzo di carte in cui vogliamo appesantire le figure in fronte. %codice%. Sommando questi, se non sappiamo che la distribuzione dei pesi è effettivamente O (n) una volta.

Questi elementi sono memorizzati in una struttura ordinata come una modifica su un skip list indicizzabile in modo tale che tutti è possibile accedere agli indici dei livelli da un determinato nodo:

   1                               10
 o---> o---------------------------------------------------------> o    Top level
   1           3              2                    5
 o---> o---------------> o---------> o---------------------------> o    Level 3
   1        2        1        2                    5
 o---> o---------> o---> o---------> o---------------------------> o    Level 2
   1     1     1     1     1     1     1     1     1     1     1 
 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    Bottom level

Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
      Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

Tuttavia, in questo caso, ogni nodo "occupa" tanto spazio quanto il suo peso.

Ora, quando cerchi una carta in questo elenco, puoi accedere alla sua posizione nell'elenco in O (log n) ora e rimuoverla dagli elenchi associati in O (1). Ok, potrebbe non essere O (1), potrebbe essere O (log log n) tempo (dovrei pensare a questo molto di più). La rimozione del sesto nodo nell'esempio precedente implicherebbe l'aggiornamento di tutti e quattro i livelli - e questi quattro livelli sono indipendenti dal numero di elementi presenti nell'elenco (a seconda di come si implementano i livelli).

Poiché il peso di un elemento è costante, si può semplicemente fare weight(card) = card.rank senza dover attraversare di nuovo la struttura.

E quindi, hai un costo una tantum di O (n) e un valore di ricerca di O (log n) e una rimozione dal costo di listino di O (1). Questo diventa O (n) + n * O (log n) + n * O (1) che offre una prestazione complessiva di O (n log n).

Vediamolo con le carte, perché è quello che ho usato sopra.

      10
top 3 -----------------------> 4d
                                .
       3             7          .
    2 ---------> 2d ---------> 4d
                  .             .
       1      2   .  3      4   .
bot 1 --> Ad --> 2d --> 3d --> 4d

Questo è un piccolo mazzo veramente con solo 4 carte in esso. Dovrebbe essere facile vedere come questo può essere esteso. Con 52 carte una struttura ideale avrebbe 6 livelli (log ₂ (52) ~ = 6), sebbene se si scavalchino gli elenchi di salto anche questo potrebbe essere ridotto ad un numero più piccolo.

La somma di tutti i pesi è 10. Quindi ottieni un numero casuale da [1 .. 10) e il suo 4 cammina l'elenco dei salti per trovare l'oggetto al soffitto (4). Poiché 4 è inferiore a 10, ti sposti dal livello superiore al secondo livello. Quattro è maggiore di 3, quindi ora siamo al 2 di quadri. 4 è inferiore a 3 + 7, quindi passiamo al livello inferiore e 4 è inferiore a 3 + 3, quindi abbiamo un 3 di quadri.

Dopo aver rimosso il 3 di quadri dalla struttura, la struttura ora appare:

       7
top 3 ----------------> 4d
                         .
       3             4   .
    2 ---------> 2d --> 4d
                  .      .
       1      2   .  4   .
bot 1 --> Ad --> 2d --> 4d

Noterai che i nodi occupano una quantità di "spazio" proporzionale al loro peso nella struttura. Ciò consente la selezione ponderata.

Poiché questo è approssimativo un albero binario bilanciato, la ricerca in questo non ha bisogno di camminare sul livello inferiore (che sarebbe O (n)) e invece andando dall'alto puoi saltare rapidamente giù per la struttura per trovare quello che stai cercando.

Molto di questo potrebbe invece essere fatto con una sorta di albero bilanciato. Il problema è che il riequilibrio della struttura quando un nodo viene rimosso diventa confuso dal momento che questa non è una classica struttura ad albero e la pulizia deve ricordare che il 4 di quadri viene ora spostato dalle posizioni [6 7 8 9] a [3 4 5 6] può costare più dei benefici della struttura ad albero.

Tuttavia, mentre l'elenco skip si avvicina ad un albero binario nella sua capacità di saltare l'elenco in O (log n) time, ha invece la semplicità di lavorare con un elenco collegato.

Questo non vuol dire che sia facile a fare tutto questo (devi comunque tenere sotto controllo tutti i link che devi modificare quando rimuovi un elemento), ma significa solo aggiornando comunque molti livelli che hai e i loro collegamenti piuttosto che tutto a destra sulla struttura ad albero corretta.