C++ lấy mẫu ngẫu nhiên các số k từ phạm vi 0: n-1 (n> k) mà không cần thay thế

Question

Tôi đang làm việc để chuyển mô phỏng MATLAB vào C++. Để làm điều này, tôi đang cố gắng sao chép randsample() function của MATLAB. Tôi đã không tìm ra một cách hiệu quả để làm điều này được nêu ra.

Vì vậy, tôi hỏi tất cả các bạn, làm cách nào để lấy mẫu k một cách ngẫu nhiên từ một phạm vi 0: n-1 (cho n> k) mà không cần thay thế trong C++?

Tôi đã xem xét các giả sau đây (lấy cảm hứng từ các ví dụ thứ ba trên cppreference.com), nhưng tôi có cảm giác như đó là một chút hacky:

initialize vect<int> v of size n 
for i = 0 to n-1 
    v[i] = i 
shuffle v 
return v[0 to k-1] 

Hạn chế ở đây cũng là yêu cầu để xây dựng một mảng lớn đầu tiên quá. Điều đó có vẻ như quá chậm/clunky overkill.

Tôi rất thích một số hướng ở đây nếu bạn có thể trợ giúp. Tôi ít quan tâm đến lý thuyết (thuật toán thú vị nhưng không liên quan đến nhu cầu của tôi bây giờ) hơn là cách tốt nhất để thực hiện điều này trong C++.

Cảm ơn trước!

Answer 1

Dưới đây là một cách tiếp cận mà không yêu cầu tạo và xáo trộn một danh sách khổng lồ, trong trường hợp N là rất lớn nhưng k không phải là:

std::vector<int> pick(int N, int k) { 
    std::random_device rd; 
    std::mt19937 gen(rd()); 

    std::unordered_set<int> elems = pickSet(N, k, gen); 

    // ok, now we have a set of k elements. but now 
    // it's in a [unknown] deterministic order. 
    // so we have to shuffle it: 

    std::vector<int> result(elems.begin(), elems.end()); 
    std::shuffle(result.begin(), result.end(), gen); 
    return result; 
} 

Bây giờ cách tiếp cận ngây thơ thực hiện pickSet là:

std::unordered_set<int> pickSet(int N, int k, std::mt19937& gen) 
{ 
    std::uniform_int_distribution<> dis(1, N); 
    std::unordered_set<int> elems; 

    while (elems.size() < k) { 
     elems.insert(dis(gen)); 
    } 

    return elems; 
} 

Nhưng nếu k lớn so với N, thuật toán này có thể dẫn đến nhiều va chạm và có thể khá chậm. Chúng ta có thể làm tốt hơn bằng cách đảm bảo rằng chúng ta có thể thêm một yếu tố trên mỗi chèn (mang đến cho bạn bởi Robert Floyd):

std::unordered_set<int> pickSet(int N, int k, std::mt19937& gen) 
{ 
    std::unordered_set<int> elems; 
    for (int r = N - k; r < N; ++r) { 
     int v = std::uniform_int_distribution<>(1, r)(gen); 

     // there are two cases. 
     // v is not in candidates ==> add it 
     // v is in candidates ==> well, r is definitely not, because 
     // this is the first iteration in the loop that we could've 
     // picked something that big. 

     if (!elems.insert(v).second) { 
      elems.insert(r); 
     } 
    } 
    return elems; 
} 

Answer 2

Bob Floyd đã tạo một thuật toán mẫu ngẫu nhiên sử dụng tập hợp. Kích thước cấu trúc trung gian tỷ lệ thuận với kích thước mẫu bạn muốn thực hiện.

Nó hoạt động bằng cách tạo ngẫu nhiên số K và thêm chúng vào bộ. Nếu một số được tạo xảy ra đã tồn tại trong tập hợp, nó sẽ đặt giá trị của bộ đếm thay vì được bảo đảm là chưa được nhìn thấy. Vì vậy, nó được đảm bảo để chạy trong thời gian tuyến tính và không đòi hỏi một cấu trúc trung gian lớn. Nó vẫn có các thuộc tính phân phối ngẫu nhiên khá tốt.

Mã này về cơ bản được lấy từ Lập trình Ngọc trai với một số sửa đổi để sử dụng C++ hiện đại hơn.

unordered_set<int> BobFloydAlgo(int sampleSize, int rangeUpperBound) 
{ 
    unordered_set<int> sample; 
    default_random_engine generator; 

    for(int d = rangeUpperBound - sampleSize; d < rangeUpperBound; d++) 
    { 
      int t = uniform_int_distribution<>(0, d)(generator); 
      if (sample.find(t) == sample.end()) 
       sample.insert(t); 
      else 
       sample.insert(d); 
    } 
    return sample; 
} 

Mã này chưa được kiểm tra.