Meilleur moyen de sélectionner un élément de tableau aléatoire en évitant la liste d'exclusion

Question

Quelle est la manière la plus élégante/efficace de sélectionner une position aléatoire dans une matrice n*n excluant un ensemble de positions ?

Exemple : Imaginez un échiquier, donc n=8 et il y a 8*8 = 64 positions au total. Il y a 3 pions aux positions (0, 0), (5, 3), (7, 4). La tâche consiste à sélectionner une position aléatoire qui n'est pas déjà occupée par les pions.

Voici ce que j'ai trouvé :

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 complexité temporelle est constante pour n et linéaire avec le nombre de cellules_occupées. Donc, si 90 % des cellules sont déjà occupées, la boucle itérera plus longtemps.

Y a-t-il une meilleure façon de faire cela?

Answer 1

Premièrement, il est clair que vous ne pouvez pas faire mieux qu'un pire cas de O(m) , où m est le nombre de cellules de la matrice, c'est-à-dire m=n² , où n est la largeur de la matrice : dans le pire des cas tous cellules sauf une sont occupées, vous devrez au moins regarder chacune de ces coordonnées m-1 .

Je dois également mentionner ici que dans votre code random_position not in occupied_positionsn'est pas une opération constante. Chaque fois que cette liste est itérée pour trouver une correspondance.

Voici une alternative :

Vous pouvez dériver le nombre de cellules libres, produire un nombre aléatoire jusqu'à cette limite, puis parcourir les cellules occupées pour adapter ce nombre (de manière incrémentielle) afin qu'il pointe vers une cellule réellement libre. Dans ce processus, le nombre correspond uniquement à une coordonnée x et y.

Pour que cela soit efficace, il faut supposer que la liste des cellules occupées est déjà triée.

Voici comment cela pourrait être codé:

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)

Ce code s'exécute en O(k) , où k est la taille de la occupied_positionsliste. Si nous ne pouvons pas garantir que cette liste est triée, nous devons d'abord la trier, ce qui détermine ensuite la complexité temporelle globale, c'est-à-dire O(klogk) .

Answer 2

Au lieu de choisir une position au hasard et de vérifier si elle est occupée, commencez par scanner le tableau pour voir quelles positions sont ouvertes. Créez une liste de ces endroits. C'est O(n)où n est le nombre total d'espaces sur le plateau. Ensuite, sélectionnez un élément aléatoire parmi les points ouverts uniquement . Notez que lorsque vous n'avez que quelques emplacements ouverts, la sélection aléatoire ne sélectionne toujours que dans un espace de quelques espaces, et vous n'aurez jamais à échantillonner au hasard qu'une seule fois.