La mejor manera de seleccionar un elemento de matriz aleatoria evitando la lista de exclusión

Aug 20 2020

¿Cuál es la forma más elegante/eficiente de seleccionar una posición aleatoria en una matriz n*n excluyendo un conjunto de posiciones?

Ejemplo: imagina un tablero de ajedrez, entonces n=8 y hay 8*8 = 64 posiciones totales. Hay 3 peones en las posiciones (0, 0), (5, 3), (7, 4). La tarea es seleccionar una posición aleatoria que no esté ya ocupada por los peones.

Esto es lo que se me ocurrió:

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 complejidad del tiempo es constante para n y lineal con el número de celdas_ocupadas. Entonces, si el 90% de las celdas ya están ocupadas, el ciclo iterará por más tiempo.

¿Hay una mejor manera de hacer esto?

Respuestas

2 trincot Aug 20 2020 at 02:06

Primero, está claro que no puede hacerlo mejor que el peor caso de O(m) , donde m es el número de celdas en la matriz, es decir, m=n² , donde n es el ancho de la matriz: en el peor de los casos, todas celdas excepto una están ocupadas, necesitará al menos mirar cada una de esas coordenadas m-1 .

También debo mencionar aquí que en su código random_position not in occupied_positionsno es una operación constante. Cada vez que se itera esa lista para encontrar una coincidencia.

Aquí hay una alternativa:

Puede derivar el número de celdas libres, producir un número aleatorio hasta ese límite y luego iterar las celdas ocupadas para adaptar ese número (incrementalmente) para apuntar a una celda realmente libre. En este proceso, el número se asigna únicamente a una coordenada xey.

Para que esto sea eficiente, debemos asumir que la lista de celdas ocupadas ya está ordenada.

Así es como se podría codificar:

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)

Este código se ejecuta en O(k) , donde k es el tamaño de la occupied_positionslista. Si no podemos garantizar que esta lista esté ordenada, primero debemos ordenarla y esto determina la complejidad temporal general, es decir, O(klogk) .

JacobSteinebronn Aug 20 2020 at 01:16

En lugar de elegir una posición al azar y verificar si está ocupada, primero escanea el tablero para ver qué posiciones están abiertas. Crea una lista de esos lugares. Aquí es O(n)donde n es el número total de espacios en el tablero. Luego, seleccione un elemento aleatorio solo de los espacios abiertos. Tenga en cuenta que cuando solo tiene unas pocas ranuras abiertas, la selección aleatoria solo selecciona de un espacio de unos pocos espacios, y solo tendrá que realizar una muestra aleatoria una vez.