Лучший способ выбрать случайный элемент массива, избегая списка исключений

Aug 20 2020

Каков наиболее элегантный / эффективный способ выбора случайной позиции в матрице n * n, исключая набор позиций?

Пример: представьте себе шахматную доску, поэтому n = 8 и всего 8 * 8 = 64 позиции. На позициях (0, 0), (5, 3), (7, 4) стоят 3 пешки. Задача - выбрать случайную позицию, которая еще не занята пешками.

Вот что я придумал:

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)

Сложность по времени постоянна для n и линейна в зависимости от количества занятых_ячейек. Таким образом, если 90% ячеек уже занято, цикл будет длиться дольше.

Есть ли лучший способ сделать это?

Ответы

2 trincot Aug 20 2020 at 02:06

Во-первых, ясно, что вы не можете добиться большего, чем наихудший случай O (m) , где m - количество ячеек в матрице, т.е. m = n² , где n - ширина матрицы: в худшем случае все ячейки, кроме одной занятой, вам нужно будет хотя бы посмотреть на каждую из этих координат m-1 .

Я также должен здесь упомянуть, что в вашем коде random_position not in occupied_positionsнет постоянной операции. Каждый раз, когда этот список повторяется, чтобы найти совпадение.

Вот альтернатива:

Вы можете получить количество свободных ячеек, произвести случайное число до этого предела, а затем итерировать занятые ячейки, чтобы адаптировать это число (постепенно), чтобы оно указывало на фактически свободную ячейку. В этом процессе число однозначно отображается в координаты x и y.

Чтобы это было эффективно, мы должны предположить, что список занятых ячеек уже отсортирован.

Вот как это можно закодировать:

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)

Этот код выполняется в O (k) , где k - размер occupied_positionsсписка. Если мы не можем гарантировать, что этот список отсортирован, то нам нужно сначала отсортировать его, а затем определить общую временную сложность, то есть O (klogk) .

JacobSteinebronn Aug 20 2020 at 01:16

Вместо того, чтобы выбирать случайную позицию и проверять, занята ли она, сначала просканируйте доску, чтобы увидеть, какие позиции открыты. Составьте список этих мест. Здесь O(n)n - общее количество мест на доске. Затем выберите случайный элемент только из открытых мест. Обратите внимание, что когда у вас есть только несколько открытых слотов, случайный выбор по-прежнему выбирается только из нескольких ячеек, и вам нужно будет выполнить случайную выборку только один раз.