Pertanyaan Jumlah sampel dengan probabilitas yang sama yang bukan bagian dari suatu himpunan


Saya punya nomor n dan satu set angka S ∈ [1..n]* dengan ukuran s (yang jauh lebih kecil dari n). Saya ingin mengambil sampel nomor k ∈ [1..n] dengan probabilitas yang sama, tetapi jumlahnya tidak diizinkan berada di lokasi S.

Saya mencoba memecahkan masalah dalam kondisi terburuk O(log n + s). Saya tidak yakin apakah itu mungkin.

Pendekatan naif adalah membuat larik angka dari 1 hingga n mengecualikan semua angka di S lalu pilih satu elemen larik. Ini akan berjalan di O(n) dan bukan pilihan.

Pendekatan lain mungkin hanya menghasilkan angka acak ∈[1..n] dan menolaknya jika mereka terkandung S. Ini tidak memiliki batasan teoretis karena nomor apa pun dapat diambil beberapa kali bahkan jika berada di lokasi. Tetapi rata-rata ini mungkin solusi praktis jika s secara substansial lebih kecil dari n.


4
2018-05-26 20:26


asal


Jawaban:


Ini adalah solusi O (1) dengan pengaturan awal O (s) yang bekerja dengan memetakan setiap nomor yang tidak diizinkan> ke nomor yang diizinkan <= s.

Membiarkan S menjadi himpunan nilai yang tidak diizinkan, S(i), dimana i = [1 .. s] dan s = |S|.

Berikut adalah algoritma dua bagian. Bagian pertama membangun tabel hash hanya berdasarkan S di O(s) waktu, bagian kedua menemukan nilai acak k ∈ {1..n}, k ∉ S di O(1) waktu, dengan asumsi kita dapat menghasilkan nomor acak seragam dalam rentang yang berdekatan dalam waktu yang konstan. Tabel hash dapat digunakan kembali untuk nilai acak baru dan juga untuk yang baru n (asumsi S ⊂ { 1 .. n } masih memegang tentu saja).

Untuk membuat hash, H. Set pertama j = 1. Kemudian ulangi S(i), unsur-unsur S. Mereka tidak perlu disortir. Jika S(i) > s, tambahkan pasangan nilai kunci (S(i), j) ke tabel hash, kecuali j ∈ S, dalam hal ini kenaikan j sampai tidak. Akhirnya, kenaikan j.

Untuk menemukan nilai acak k, pertama menghasilkan nilai acak seragam dalam rentang s + 1 untuk n, inklusif. Jika k adalah kunci masuk H, kemudian k = H(k). Yaitu, kami melakukan paling banyak satu hash pencarian untuk memastikan k tidak ada S.

Kode Python untuk menghasilkan hash:

def substitute(S):
    H = dict()
    j = 1
    for s in S:
        if s > len(S):
            while j in S: j += 1
            H[s] = j
            j += 1
    return H

Untuk implementasi yang sebenarnya menjadi O (s), seseorang mungkin perlu mengkonversi S menjadi sesuatu seperti frozenset untuk memastikan tes untuk keanggotaan adalah O (1) dan juga memindahkan len(S) loop invariant keluar dari loop. Dengan asumsi j in S tes dan penyisipan ke dalam hash (H[s] = j) adalah waktu yang konstan, ini harus memiliki kompleksitas O (s).

Generasi dari nilai acak hanyalah:

def myrand(n, s, H):
    k = random.randint(s + 1, n)
    return (H[k] if k in H else k)

Jika seseorang hanya tertarik pada satu nilai acak per S, maka algoritma dapat dioptimalkan untuk memperbaiki kasus umum, sementara kasus terburuk tetap sama. Ini masih membutuhkan S berada dalam tabel hash yang memungkinkan untuk "elemen" uji waktu konstan.

def rand_not_in(n, S):
    k = random.randint(len(S) + 1, n);
    if k not in S: return k
    j = 1
    for s in S:
        if s > len(S):
            while j in S: j += 1
            if s == k: return j
            j += 1

Pengoptimalan adalah: Hanya menghasilkan pemetaan jika nilai acak dalam S. Jangan simpan pemetaan ke tabel hash. Hubung singkat generasi pemetaan ketika nilai acak ditemukan.


4
2018-05-27 07:53



Katakanlah disortir. Hasilkan angka acak antara 1 dan n-s, sebut saja k. Kami telah memilih elemen k'th {1, ..., n} - s. Sekarang kita harus menemukannya.

Gunakan pencarian biner pada s untuk menemukan jumlah elemen s <= k. Ini mengambil O (log | s |). Tambahkan ini ke k. Dengan demikian, kita mungkin telah lulus atau tiba di elemen tambahan s. Kita dapat menyesuaikan ini dengan menambah jawaban kita untuk setiap elemen yang kita lewati, yang kita temukan dengan memeriksa elemen lebih besar selanjutnya dari titik yang kita temukan dalam pencarian biner kita.

Misalnya, n = 100, s = {1,4,5,22}, dan nomor acak kami adalah 3. Jadi pendekatan kami harus mengembalikan elemen ketiga [2,3,6,7, ..., 21,23 , 24, ..., 100] yang merupakan 6. Pencarian biner menemukan bahwa 1 elemen paling banyak 3, jadi kita naik ke 4. Sekarang kita bandingkan dengan elemen yang lebih besar berikutnya yaitu 4 jadi kenaikan ke 5. Mengulangi ini menemukan 5 jadi kami menambah ke 6. Kami memeriksa sekali lagi, melihat bahwa 6 tidak ada di dalamnya, jadi kami berhenti.

Misalnya, n = 100, s = {1,4,5,22}, dan nomor acak kami adalah 4. Jadi pendekatan kami harus mengembalikan elemen keempat [2,3,6,7, ..., 21,23 , 24, ..., 100] yang merupakan 7. Pencarian biner menemukan bahwa 2 elemen paling banyak 4, jadi kita bertambah menjadi 6. Sekarang kita bandingkan dengan elemen yang lebih besar berikutnya yaitu 5 sehingga kenaikan menjadi 7. Kami memeriksa Sekali lagi, lihat bahwa angka berikutnya adalah> 7, jadi kami berhenti.

Jika kita berasumsi bahwa "s jauh lebih kecil dari n" berarti | s | <= log (n), maka kita akan menaikkan pada sebagian besar log (n) kali, dan dalam hal apapun pada kebanyakan waktu.


Jika s tidak diurutkan maka kita bisa melakukan hal berikut. Buat array bit ukuran s. Hasilkan k. Parse dan lakukan dua hal: 1) hitung jumlah elemen <k, panggil r ini. Pada saat yang sama, atur bit i'th ke 1 jika k + i dalam s (0 diindeks jadi jika k dalam s maka bit pertama diatur).

Sekarang, kenaikan k beberapa kali sama dengan r ditambah jumlah bit yang diset adalah larik dengan indeks <= jumlah kali yang bertambah.

Misalnya, n = 100, s = {1,4,5,22}, dan nomor acak kami adalah 4. Jadi pendekatan kami harus mengembalikan elemen keempat [2,3,6,7, ..., 21,23 , 24, ..., 100] yaitu 7. Kami mengurai dan 1) perhatikan bahwa 1 elemen di bawah 4 (r = 1), dan 2) atur array ke [1, 1, 0, 0]. Kami menambah sekali untuk r = 1 dan tambahan dua kali untuk dua bit set, berakhir pada 7.

Ini adalah waktu O (s), ruang O (s).


5
2018-05-26 20:41



Sebenarnya, metode penolakan tampaknya seperti pendekatan praktis. Hasilkan angka dalam 1...n dan periksa apakah itu terlarang; regenerasi sampai nomor yang dihasilkan tidak terlarang.

Probabilitas penolakan tunggal adalah p = s/n. Dengan demikian jumlah bilangan acak yang diharapkan adalah 1 + p + p^2 + p^3 + ...  yang mana  1/(1-p), yang pada gilirannya sama dengan n/(n-s).

Sekarang, jika s jauh lebih sedikit daripada n, atau bahkan lebih s = n/2, jumlah yang diharapkan ini paling banyak 2. Itu akan membutuhkan s hampir sama dengan n untuk membuatnya praktis dalam praktek.

Kalikan waktu yang diharapkan dengan log s jika Anda menggunakan set-pohon untuk memeriksa apakah nomornya ada di set, atau hanya dengan benar 1(nilai yang diharapkan lagi) jika itu adalah hash-set. Jadi waktu rata-rata adalah O(1) atau O(log s) tergantung pada implementasi yang ditetapkan. Ada juga O(s) memori untuk menyimpan set, tetapi kecuali set diberikan dalam beberapa cara khusus, secara implisit dan ringkas, saya tidak melihat bagaimana hal itu dapat dihindari.

(Edit: Sesuai komentar, Anda melakukan ini hanya sekali untuk satu set tertentu. Jika, selain itu, kita kurang beruntung, dan set diberikan sebagai array atau daftar biasa, bukan struktur data yang lebih bagus, kita mendapatkan O(s) waktu yang diharapkan dengan pendekatan ini, yang masih cocok dengan O(log n + s) kebutuhan.)

Jika serangan terhadap algoritma tak terbatas menjadi perhatian (dan hanya jika benar-benar ada), metode ini dapat menyertakan algoritme mundur-mundur untuk kasus ketika sejumlah iterasi tetap tertentu tidak memberikan jawabannya. Demikian pula caranya IntroSort adalah QuickSort tetapi jatuh kembali ke HeapSort jika kedalaman rekursi terlalu tinggi (yang hampir pasti merupakan hasil dari serangan yang menghasilkan perilaku QuickSort kuadratik).


3
2018-05-26 22:15



  1. Temukan semua angka yang berada dalam kumpulan terlarang dan kurang atau sama dengan itu n-s. Sebut itu array A.
  2. Temukan semua angka yang tidak dalam set terlarang dan lebih besar lagi n-s. Sebut saja array B. Ini dapat dilakukan dalam O (s) jika set disortir.
  3. Perhatikan bahwa panjang A dan B sama, dan buat pemetaan map[A[i]] = B[i]
  4. Hasilkan angka t hingga n-s. Jika ada map[t] kembalikan, jika tidak kembalikan t

Ini akan berhasil O(s) sisipan ke peta + 1 lookup yang rata-rata O (s) atau O(s log s)


2
2018-05-26 22:36