Saya punya, misalnya, tabel ini
+ ----------------- + | buah | berat | + ----------------- + | apel | 4 | | oranye | 2 | | lemon | 1 | + ----------------- +
Saya perlu mengembalikan buah acak. Tetapi apel harus dipetik 4 kali lebih sering dari Lemon dan 2 kali lebih sering dari jeruk .
Dalam kasus yang lebih umum, harus f(weight)
sering kali.
Apa algoritma umum yang baik untuk menerapkan perilaku ini?
Atau mungkin ada beberapa permata siap pakai di Ruby? :)
PS
Saya sudah menerapkan algoritma saat ini di Ruby https://github.com/fl00r/pickup
algorithms
ruby
math
random
fl00r
sumber
sumber
Jawaban:
Solusi yang paling sederhana secara konseptual adalah membuat daftar di mana setiap elemen terjadi sebanyak beratnya, jadi
Kemudian gunakan fungsi apa pun yang Anda miliki untuk memilih elemen acak dari daftar itu (misalnya menghasilkan indeks acak dalam kisaran yang tepat). Ini tentu saja tidak sangat efisien memori dan membutuhkan bobot integer.
Pendekatan lain yang sedikit lebih rumit akan terlihat seperti ini:
Hitung jumlah bobot kumulatif:
Jika indeks di bawah 4 mewakili apel , 4 di bawah 6 jeruk dan 6 di bawah 7 lemon .
Hasilkan nomor acak
n
dalam kisaran0
hinggasum(weights)
.n
. Buah yang sesuai adalah hasil Anda.Pendekatan ini membutuhkan kode yang lebih rumit daripada yang pertama, tetapi lebih sedikit memori dan komputasi dan mendukung bobot titik-mengambang.
Untuk kedua algoritma, langkah-setup dapat dilakukan satu kali untuk jumlah acak pilihan.
sumber
Berikut adalah algoritma (dalam C #) yang dapat memilih elemen tertimbang acak dari urutan apa pun, hanya mengulanginya sekali saja:
Ini didasarkan pada alasan berikut: mari pilih elemen pertama dari urutan kami sebagai "hasil saat ini"; kemudian, pada setiap iterasi, simpan atau buang dan pilih elemen baru sebagai yang sekarang. Kita dapat menghitung probabilitas setiap elemen yang diberikan untuk dipilih pada akhirnya sebagai produk dari semua probabilitas yang tidak akan dibuang dalam langkah-langkah berikutnya, kali probabilitas bahwa itu akan dipilih di tempat pertama. Jika Anda menghitung, Anda akan melihat bahwa produk ini disederhanakan menjadi (bobot elemen) / (jumlah semua bobot), yang persis seperti yang kami butuhkan!
Karena metode ini hanya mengulangi urutan input sekali saja, metode ini bekerja bahkan dengan urutan yang sangat besar, asalkan jumlah bobot cocok menjadi
int
(atau Anda dapat memilih jenis yang lebih besar untuk penghitung ini)sumber
Sudah ada jawaban yang bagus dan saya akan sedikit mengembangkannya.
Seperti yang disarankan Benjamin, jumlah kumulatif biasanya digunakan dalam masalah seperti ini:
Untuk menemukan item dalam struktur ini, Anda dapat menggunakan sesuatu seperti sepotong kode Nevermind. Sepotong kode C # yang biasa saya gunakan:
Sekarang ke bagian yang menarik. Seberapa efisien pendekatan ini dan solusi apa yang paling efisien? Sepotong kode saya membutuhkan O (n) memori dan berjalan dalam waktu O (n) . Saya tidak berpikir itu bisa dilakukan dengan kurang dari O (n) ruang tetapi kompleksitas waktu bisa jauh lebih rendah, O (log n) sebenarnya. Caranya adalah dengan menggunakan pencarian biner daripada biasa untuk loop.
Ada juga cerita tentang memperbarui bobot. Dalam kasus terburuk, memperbarui bobot untuk satu elemen menyebabkan pembaruan jumlah kumulatif untuk semua elemen meningkatkan kompleksitas pembaruan ke O (n) . Itu juga dapat ditebang ke O (log n) menggunakan pohon indeks biner .
sumber
Ini adalah implementasi Python sederhana:
dan
Dalam algoritme genetik, prosedur pemilihan ini disebut sebagai Pemilihan proporsi proporsional atau Pemilihan Roda Roulette sejak:
Algoritma tipikal memiliki kompleksitas O (N) atau O (log N) tetapi Anda juga dapat melakukan O (1) (mis. Pemilihan roda Roulette melalui penerimaan stokastik ).
sumber
Inti ini melakukan persis apa yang Anda minta.
Anda bisa menggunakannya seperti itu:
Kode di atas kemungkinan besar (% 98) menghasilkan 0 yang merupakan indeks 'apel' untuk larik yang diberikan.
Kode ini juga menguji metode yang disediakan di atas:
Ini memberikan output seperti itu:
sumber