algorithm - 选择随机数组元素避免排除列表的最佳方法

Question

在不包括一组位置的 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% 的单元格已被占用，则循环将迭代更长的时间。

有没有更好的方法来做到这一点？

标签： algorithm

Answer 1

首先，很明显，你不能比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)。