Cara terbaik untuk memilih elemen array acak menghindari daftar pengecualian

Question

Apa cara yang paling elegan / efisien untuk memilih posisi acak dalam matriks n * n tidak termasuk satu set posisi?

Contoh: Bayangkan sebuah papan catur, jadi n = 8 dan ada total 8 * 8 = 64 posisi. Ada 3 bidak di posisi (0, 0), (5, 3), (7, 4). Tugasnya adalah memilih posisi acak yang belum ditempati oleh bidak.

Inilah yang saya dapatkan:

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)

Kompleksitas waktu konstan untuk n dan linier dengan jumlah sel yang ditempati. Jadi jika 90% sel sudah terisi, loop akan melakukan iterasi lebih lama.

Apakah ada cara yang lebih baik untuk melakukan ini?

Answer 1

Pertama, jelas bahwa Anda tidak dapat melakukan yang lebih baik daripada kasus terburuk O (m) , di mana m adalah jumlah sel dalam matriks, yaitu m = n² , di mana n adalah lebar matriks: dalam kasus terburuk semua kecuali satu sel terisi, Anda akan membutuhkan setidaknya untuk melihat masing-masing koordinat m-1 tersebut .

Saya juga harus menyebutkan di sini bahwa dalam kode Anda random_position not in occupied_positionsbukanlah operasi yang konstan. Setiap kali daftar itu diulang untuk menemukan kecocokan.

Berikut ini alternatifnya:

Anda dapat memperoleh jumlah sel bebas, menghasilkan angka acak hingga batas tersebut, dan kemudian mengulang sel yang ditempati untuk menyesuaikan jumlah tersebut (secara bertahap) untuk menunjuk ke sel yang sebenarnya bebas. Dalam proses ini angka dipetakan secara unik ke koordinat x dan y.

Agar ini efisien, kita harus mengasumsikan bahwa daftar sel yang ditempati sudah diurutkan.

Berikut adalah cara yang dapat dikodekan:

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)

Kode ini berjalan di O (k) , di mana k adalah ukuran occupied_positionsdaftar. Jika kita tidak dapat menjamin bahwa daftar ini diurutkan, maka kita perlu mengurutkannya terlebih dahulu, dan ini kemudian menentukan kompleksitas waktu secara keseluruhan, yaitu O (klogk) .

Answer 2

Alih-alih memilih posisi acak dan memeriksa apakah sudah terisi, pertama-tama pindai papan untuk melihat posisi mana yang terbuka. Buat daftar tempat-tempat itu. Di O(n)sinilah n adalah jumlah total ruang papan. Kemudian, pilih elemen acak hanya dari tempat terbuka. Perhatikan bahwa ketika Anda hanya memiliki beberapa slot terbuka, pemilihan acak masih hanya mengambil dari beberapa spasi, dan Anda hanya perlu sampel acak sekali.