Quiz: Tìm số ngẫu nhiên

Cho một file chứa rất lớn số lượng số tự nhiên (số lượng N bạn không biết trước).
Làm thế nào để thiết kế 1 thuật toán đọc qua file 1 lần duy nhất theo từng dòng một (sequential read) và chọn ngẫu nhiên 1 số trong đó sao cho xác suất mỗi phần tử được chọn là bằng nhau (bằng 1/N).

Mấy tuần trước e có đi ngày hội doanh nghiệp trong trường thì được hỏi 1 câu nv, e chỉ nghĩ được là bỏ vào std::set xong chọn ra ngẫu nhiên 1 phần tử thì xác suất sẽ bằng nhau, nhưng nv thì vẫn chưa thỏa điều kiện =1/N)

em xài

spoilier

https://en.wikipedia.org/wiki/Reservoir_sampling

code chạy thử:

#include <ctime>
#include <iostream>
#include <iterator>
#include <random>
#include <sstream>

template <class InputIt, class URBG>
auto randomChoice1(InputIt first, InputIt last, URBG&& g) {
    using result_t = typename InputIt::value_type;
    result_t result = *first++;
    for (size_t i = 1; first != last; ++i, ++first) {
        size_t j = std::uniform_int_distribution<size_t>{0, i}(g);
        if (j < 1) result = *first;
    }
    return result;
}

int main() {
    std::mt19937 g(time(0));
    int freq[10] = {0};
    for (int i = 0; i < 100000; ++i) {
        std::istringstream iss("0 1 2 3 4 5 6 7 8 9");
        freq[randomChoice1(std::istream_iterator<int>(iss),
                           std::istream_iterator<int>(), g)]++;
    }
    for (int i = 0; i < 10; ++i) std::cout << i << ": " << freq[i] << "\n";
}

https://rextester.com/VVU76667
sample output:

0: 10131
1: 9984
2: 9996
3: 9991
4: 9890
5: 9992
6: 10007
7: 9987
8: 9956
9: 10066
4 Likes

Spoiler pls :smiley:

Gợi ý: bạn sẽ phải chọn N lần.

5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?