Số ngẫu nhiên dựa trên xác suất

Question

Tôi đang gặp sự cố khi tạo các số ngẫu nhiên không tuân theo phân bố đồng nhất rời rạc.

Ví dụ: giả sử tôi có 5 số (để đơn giản), xác suất số k được tạo sẽ là k/15. (K = 1-5)

Ý tưởng của tôi là để tạo ra một số j ngẫu nhiên sử dụng rand(), và nếu con số này j là:

1 => sau đó số 1 được tạo ra

2 hoặc 3 => num 2

4 hoặc 5 hoặc 6 => num 3

7 hoặc 8 hoặc 9 hoặc 10 => num 4

11 hoặc 12 hoặc 13 hoặc 14 hoặc 15 => num 5

Bây giờ hãy chia tỷ lệ này để tạo ra 1-10, 1-100, 1-1000. Điều này có hoạt động theo cách tôi dự định không? Tôi đã xây dựng một vòng lặp mà khá nhiều hiện điều này mỗi khi một số cần phải được tạo ra, tôi nghĩ rằng nó có thể không hiệu quả kể từ khi nó đi lên cho đến khi nó tìm thấy số j tạo ra trong một trong các phạm vi ... Điều gì có thể là một cách tốt hơn để làm điều này?

CHỈNH SỬA: hoặc có thể tạo một mảng một lần với số thích hợp và sau đó kéo ra bằng rand() giải pháp tốt hơn?

Answer 1

Hãy xem xét rằng tổng s các số nguyên từ 1 đến n là s = n * (n + 1)/2. Giải quyết cho n để nhận n = (± sqrt(8*s + 1) - 1)/2. Chúng ta có thể bỏ qua căn bậc hai âm, như chúng ta biết n là dương. Do đó n = (sqrt(8*s + 1) - 1)/2.

Vì vậy, cắm vào các số nguyên cho s giữa 1 và 15:

s n 
01 1.000000 
02 1.561553 
03 2.000000 
04 2.372281 
05 2.701562 
06 3.000000 
07 3.274917 
08 3.531129 
09 3.772002 
10 4.000000 
11 4.216991 
12 4.424429 
13 4.623475 
14 4.815073 
15 5.000000 

Nếu chúng ta lấy trần của mỗi tính n (số nguyên nhỏ nhất không ít hơn n), chúng tôi có được điều này:

s n 
01 1 
02 2 
03 2 
04 3 
05 3 
06 3 
07 4 
08 4 
09 4 
10 4 
11 5 
12 5 
13 5 
14 5 
15 5 

Vì vậy, bạn có thể chuyển từ phân phối đồng đều sang phân phối của bạn theo không gian cố định và thời gian không đổi (không lặp lại và không có bảng được tính trước):

double my_distribution_from_uniform_distribution(double s) { 
    return ceil((sqrt(8*s + 1) - 1)/2); 
} 

N.B. Điều này dựa trên sqrt cho kết quả chính xác cho một hình vuông hoàn hảo (ví dụ:trả lại chính xác 7 cho đúng 49). Điều này thường là một giả định an toàn, bởi vì IEEE 754 yêu cầu làm tròn chính xác các rễ vuông.

Đôi 754 IEEE có thể đại diện cho tất cả các số nguyên từ 1 đến 2^53 (và nhiều số nguyên lớn hơn, nhưng không tiếp tục sau 2^53). Vì vậy, chức năng này sẽ hoạt động chính xác cho tất cả s từ 1 đến floor((2^53 - 1)/8) = 1125899906842623.

Answer 2

Bạn có thể tận dụng lợi thế của thực tế số học tò mò rằng:

S(n) = 1 + 2 + 3 + ... + (n - 1) + n 

hoặc đơn giản:

S(n) = n * (n + 1)/2 

này cho phép bạn tránh lưu trữ mảng.

Answer 3

Bạn dường như đi đúng hướng, nhưng C++ đã có một bản phân phối số ngẫu nhiên chuyên ngành cho rằng, std::discrete_distribution

#include <iostream> 
#include <vector> 
#include <map> 
#include <random> 

int main() 
{ 
    std::random_device rd; 
    std::mt19937 gen(rd()); 

    // list of probabilities  
    std::vector<double> p = {0, 1.0/15, 2.0/15, 3.0/15, 4.0/15, 5.0/15}; 
    // could also be min, max, and a generating function (n/15 in your case?) 
    std::discrete_distribution<> d(p.begin(), p.end()); 

    // some statistics 
    std::map<int, int> m; 
    for(int n=0; n<10000; ++n) { 
     ++m[d(gen)]; 
    } 
    for(auto p : m) { 
     std::cout << p.first << " generated " << p.second << " times\n"; 
    } 
} 

demo trực tuyến: http://ideone.com/jU1ll