dapatkan item acak berbobot

51

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

fl00r
sumber
11
yang seharusnya menjadi formula yang sama untuk mendapatkan rampasan acak di Diablo :-)
Jalayn
1
@Jalayn: Sebenarnya, ide untuk solusi interval dalam jawaban saya di bawah ini berasal dari apa yang saya ingat tentang tabel pertempuran di World of Warcraft. :-D
Benjamin Kloster
Lihat juga
BlueRaja - Danny Pflughoeft
Saya telah menerapkan beberapa algoritma acak sederhana berbobot . Beri tahu saya jika Anda memiliki pertanyaan.
Leonid Ganeline

Jawaban:

50

Solusi yang paling sederhana secara konseptual adalah membuat daftar di mana setiap elemen terjadi sebanyak beratnya, jadi

fruits = [apple, apple, apple, apple, orange, orange, lemon]

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:

  1. Hitung jumlah bobot kumulatif:

    intervals = [4, 6, 7]

    Jika indeks di bawah 4 mewakili apel , 4 di bawah 6 jeruk dan 6 di bawah 7 lemon .

  2. Hasilkan nomor acak ndalam kisaran 0hingga sum(weights).

  3. Temukan item terakhir yang jumlah kumulatifnya di atas 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.

Benjamin Kloster
sumber
2
solusi intervalnya tampak bagus
Jalayn
1
Ini adalah pikiran pertama saya :). Tapi bagaimana kalau saya punya meja dengan 100 buah dan beratnya bisa sekitar 10rb? Ini akan menjadi array yang sangat besar dan ini tidak akan seefisien yang saya inginkan. Ini tentang solusi pertama. Solusi kedua terlihat bagus
fl00r
1
Saya telah mengimplementasikan algoritma ini di Ruby github.com/fl00r/pickup
fl00r
1
metode alias adalah cara defacto untuk menangani hal ini. Saya benar-benar heran dengan jumlah posting yang mengulang kode yang sama berulang-ulang, sambil mengabaikan metode alias . demi Tuhan Anda mendapatkan kinerja waktu yang konstan!
opa
30

Berikut adalah algoritma (dalam C #) yang dapat memilih elemen tertimbang acak dari urutan apa pun, hanya mengulanginya sekali saja:

public static T Random<T>(this IEnumerable<T> enumerable, Func<T, int> weightFunc)
{
    int totalWeight = 0; // this stores sum of weights of all elements before current
    T selected = default(T); // currently selected element
    foreach (var data in enumerable)
    {
        int weight = weightFunc(data); // weight of current element
        int r = Random.Next(totalWeight + weight); // random value
        if (r >= totalWeight) // probability of this is weight/(totalWeight+weight)
            selected = data; // it is the probability of discarding last selected element and selecting current one instead
        totalWeight += weight; // increase weight sum
    }

    return selected; // when iterations end, selected is some element of sequence. 
}

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)

Lupakan
sumber
2
Saya akan membandingkan ini sebelum mengasumsikan lebih baik hanya karena itu sekali saja. Menghasilkan banyak nilai acak juga tidak cepat.
Jean-Bernard Pellerin
1
@ Jean-Bernard Pellerin saya lakukan, dan itu sebenarnya lebih cepat pada daftar besar. Kecuali jika Anda menggunakan generator acak yang kuat secara kriptografis (-8
Nevermind
Seharusnya jawaban imo diterima. Saya suka ini lebih baik daripada pendekatan "interval" dan "entri berulang".
Vivin Paliath
2
Saya hanya ingin mengatakan saya telah kembali ke utas ini 3 atau 4 kali dalam beberapa tahun terakhir untuk menggunakan metode ini. Metode ini telah berulang kali berhasil memberikan jawaban yang saya butuhkan dengan cukup cepat untuk tujuan saya. Saya berharap saya dapat mengangkat jawaban ini setiap kali saya kembali untuk menggunakannya.
Jim Yarbro
1
Solusi yang bagus jika Anda benar-benar hanya perlu memilih sekali. Kalau tidak, melakukan persiapan untuk solusi di jawaban pertama sekali jauh lebih efisien.
Deduplicator
22

Sudah ada jawaban yang bagus dan saya akan sedikit mengembangkannya.

Seperti yang disarankan Benjamin, jumlah kumulatif biasanya digunakan dalam masalah seperti ini:

+------------------------+
| fruit  | weight | csum |
+------------------------+
| apple  |   4    |   4  |
| orange |   2    |   6  |
| lemon  |   1    |   7  |
+------------------------+

Untuk menemukan item dalam struktur ini, Anda dapat menggunakan sesuatu seperti sepotong kode Nevermind. Sepotong kode C # yang biasa saya gunakan:

double r = Random.Next() * totalSum;
for(int i = 0; i < fruit.Count; i++)
{
    if (csum[i] > r)
        return fruit[i];
}

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.

double r = Random.Next() * totalSum;
int lowGuess = 0;
int highGuess = fruit.Count - 1;

while (highGuess >= lowGuess)
{
    int guess = (lowGuess + highGuess) / 2;
    if ( csum[guess] < r)
        lowGuess = guess + 1;
    else if ( csum[guess] - weight[guess] > r)
        highGuess = guess - 1;
    else
        return fruit[guess];
}

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 .

Kaisar Orionii
sumber
Poin bagus tentang pencarian biner
fl00r
Jawaban Nevermind tidak membutuhkan ruang tambahan, jadi ini O (1), tetapi menambahkan kompleksitas runtime dengan berulang kali menghasilkan angka acak dan mengevaluasi fungsi bobot (yang, tergantung pada masalah yang mendasarinya, bisa mahal).
Benjamin Kloster
1
Apa yang Anda klaim sebagai "versi yang lebih mudah dibaca" dari kode saya sebenarnya tidak. Kode Anda perlu mengetahui jumlah total bobot, dan jumlah kumulatif, di muka; punyaku tidak.
Nevermind
@Benjamin Kloster Kode saya hanya memanggil fungsi bobot satu kali per elemen - Anda tidak bisa melakukan yang lebih baik dari itu. Anda benar tentang angka acak.
Nevermind
@Nevermind: Anda hanya memanggilnya sekali per panggilan ke fungsi pilih, jadi jika pengguna menyebutnya dua kali, fungsi bobot dipanggil lagi untuk setiap elemen. Tentu saja Anda bisa menyimpannya, tetapi Anda bukan O (1) untuk kompleksitas ruang lagi.
Benjamin Kloster
8

Ini adalah implementasi Python sederhana:

from random import random

def select(container, weights):
    total_weight = float(sum(weights))
    rel_weight = [w / total_weight for w in weights]

    # Probability for each element
    probs = [sum(rel_weight[:i + 1]) for i in range(len(rel_weight))]

    slot = random()
    for (i, element) in enumerate(container):
        if slot <= probs[i]:
            break

    return element

dan

population = ['apple','orange','lemon']
weights = [4, 2, 1]

print select(population, weights)

Dalam algoritme genetik, prosedur pemilihan ini disebut sebagai Pemilihan proporsi proporsional atau Pemilihan Roda Roulette sejak:

  • proporsi roda ditetapkan untuk masing-masing pilihan yang mungkin berdasarkan nilai bobotnya. Ini dapat dicapai dengan membagi bobot seleksi dengan bobot total semua seleksi, sehingga menormalkannya menjadi 1.
  • kemudian pemilihan acak dibuat mirip dengan bagaimana roda roulette diputar.

Pemilihan roda roulette

Algoritma tipikal memiliki kompleksitas O (N) atau O (log N) tetapi Anda juga dapat melakukan O (1) (mis. Pemilihan roda Roulette melalui penerimaan stokastik ).

manlio
sumber
Tahukah Anda apa sumber asli untuk gambar ini? Saya ingin menggunakannya untuk makalah tetapi perlu memastikan atribusi.
Malcolm MacLeod
@ MalcolmMacLeod Maaf, ini digunakan di banyak makalah / situs GA tapi saya tidak tahu siapa penulisnya.
manlio
0

Inti ini melakukan persis apa yang Anda minta.

public static Random random = new Random(DateTime.Now.Millisecond);
public int chooseWithChance(params int[] args)
    {
        /*
         * This method takes number of chances and randomly chooses
         * one of them considering their chance to be choosen.    
         * e.g. 
         *   chooseWithChance(0,99) will most probably (%99) return 1
         *   chooseWithChance(99,1) will most probably (%99) return 0
         *   chooseWithChance(0,100) will always return 1.
         *   chooseWithChance(100,0) will always return 0.
         *   chooseWithChance(67,0) will always return 0.
         */
        int argCount = args.Length;
        int sumOfChances = 0;

        for (int i = 0; i < argCount; i++) {
            sumOfChances += args[i];
        }

        double randomDouble = random.NextDouble() * sumOfChances;

        while (sumOfChances > randomDouble)
        {
            sumOfChances -= args[argCount -1];
            argCount--;
        }

        return argCount-1;
    }

Anda bisa menggunakannya seperti itu:

string[] fruits = new string[] { "apple", "orange", "lemon" };
int choosenOne = chooseWithChance(98,1,1);
Console.WriteLine(fruits[choosenOne]);

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:

Console.WriteLine("Start...");
int flipCount = 100;
int headCount = 0;
int tailsCount = 0;

for (int i=0; i< flipCount; i++) {
    if (chooseWithChance(50,50) == 0)
        headCount++;
    else
        tailsCount++;
}

Console.WriteLine("Head count:"+ headCount);
Console.WriteLine("Tails count:"+ tailsCount);

Ini memberikan output seperti itu:

Start...
Head count:52
Tails count:48
Ramazan POLAT
sumber
2
Programmer adalah tentang pertanyaan konseptual dan jawaban diharapkan dapat menjelaskan banyak hal. Melempar kesedihan alih-alih penjelasannya seperti menyalin kode dari IDE ke papan tulis: mungkin terlihat biasa dan bahkan terkadang dapat dimengerti, tetapi rasanya aneh ... hanya aneh. Papan tulis tidak memiliki kompiler
nyamuk
Anda benar, saya fokus pada kode jadi saya lupa memberi tahu cara kerjanya. Saya akan menambahkan penjelasan tentang cara kerjanya.
Ramazan Polat