除外リストを回避してランダムな配列要素を選択する最良の方法
位置のセットを除いて、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は全て最悪の場合：行列の幅であります1つを除くセルが占有されている場合は、少なくともこれらの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は総ボードスペースの数です。次に、オープンスポットのみからランダムな要素を選択します。空きスロットが数個しかない場合でも、ランダム選択は数個のスペースから選択するだけであり、ランダムにサンプリングする必要があるのは1回だけであることに注意してください。