Лучший способ выбрать случайный элемент массива, избегая списка исключений
Каков наиболее элегантный / эффективный способ выбора случайной позиции в матрице 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% ячеек уже занято, цикл будет длиться дольше.
Есть ли лучший способ сделать это?
Ответы
Во-первых, ясно, что вы не можете добиться большего, чем наихудший случай 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) .
Вместо того, чтобы выбирать случайную позицию и проверять, занята ли она, сначала просканируйте доску, чтобы увидеть, какие позиции открыты. Составьте список этих мест. Здесь O(n)
n - общее количество мест на доске. Затем выберите случайный элемент только из открытых мест. Обратите внимание, что когда у вас есть только несколько открытых слотов, случайный выбор по-прежнему выбирается только из нескольких ячеек, и вам нужно будет выполнить случайную выборку только один раз.