Il modo migliore per selezionare l'elemento dell'array casuale evitando l'elenco di esclusione

Question

Qual è il modo più elegante/efficiente per selezionare una posizione casuale in una matrice n*n escludendo un insieme di posizioni?

Esempio: Immagina una scacchiera, quindi n=8 e ci sono 8*8 = 64 posizioni totali. Ci sono 3 pedoni nelle posizioni (0, 0), (5, 3), (7, 4). Il compito è selezionare una posizione casuale che non sia già occupata dalle pedine.

Questo è quello che mi è venuto in mente:

def get_random_position(n, occupied_positions):
    while True:
        random_position = (random.choice(range(n)), random.choice(range(n)))
        if random_position not in occupied_positions:
            return random_position
    
    
if __name__ == '__main__':
    unoccupied_random_position = get_random_position(8, [(0, 0), (5, 3), (7, 4)])
    print(unoccupied_random_position)

La complessità temporale è costante per n e lineare con il numero di celle_occupate. Quindi, se il 90% delle celle è già occupato, il ciclo itererà più a lungo.

C'è un modo migliore per farlo?

Answer 1

Innanzitutto, è chiaro che non si può fare di meglio di un caso peggiore di O(m) , dove m è il numero di celle della matrice, cioè m=n² , dove n è la larghezza della matrice: nel caso peggiore tutte le celle tranne una sono occupate, dovrai almeno guardare ciascuna di quelle coordinate m-1 .

Dovrei anche menzionare qui che nel tuo codice random_position not in occupied_positionsnon è un'operazione costante. Ogni volta che l'elenco viene iterato per trovare una corrispondenza.

Ecco un'alternativa:

Potresti derivare il numero di celle libere, produrre un numero casuale fino a quel limite e quindi iterare le celle occupate per adattare quel numero (in modo incrementale) per puntare a una cella effettivamente libera. In questo processo il numero viene mappato in modo univoco su una coordinata x e y.

Perché ciò sia efficiente, dobbiamo presumere che l'elenco delle celle occupate sia già ordinato.

Ecco come potrebbe essere codificato:

def get_random_position(n, occupied_positions):
    rnd = random.randint(0, n*n - 1 - len(occupied_positions))
    for (row, col) in occupied_positions:
        if rnd < row*n+col:
            break
        rnd += 1
    return (rnd // n, rnd % n)

Questo codice viene eseguito in O(k) , dove k è la dimensione occupied_positionsdell'elenco. Se non possiamo garantire che questo elenco sia ordinato, dobbiamo prima ordinarlo e questo determina la complessità temporale complessiva, ovvero O(klogk) .

Answer 2

Invece di scegliere una posizione casuale e controllare se è occupata, scansiona prima il tabellone per vedere quali posizioni sono aperte. Crea un elenco di quei punti. Qui è O(n)dove n è il numero di spazi totali sul tabellone. Quindi, seleziona un elemento casuale solo dagli spazi aperti. Nota che quando hai solo pochi slot aperti, la selezione casuale continua a prelevare solo da uno spazio di pochi spazi e dovrai campionare a caso solo una volta.