Chọn một tập hợp con ngẫu nhiên duy nhất từ ​​một tập hợp các giá trị duy nhất

Question

C++. Visual Studio 2010.

Tôi có std::vector V của N yếu tố độc đáo (nặng cấu trúc). Làm thế nào hiệu quả có thể chọn M ngẫu nhiên, độc đáo, các yếu tố từ nó?

Ví dụ: V gồm 10 yếu tố: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} và tôi chọn ba ...

• 4, 0, 9
• 0, 7 , 8
• Nhưng KHÔNG PHẢI là: 0, 5, 5 < --- không phải là duy nhất!

STL được ưu tiên. Vì vậy, một cái gì đó như thế này?

std::minstd_rand gen; // linear congruential engine?? 
std::uniform_int<int> unif(0, v.size() - 1); 
gen.seed((unsigned int)time(NULL)); 

// ...? 

// Or is there a good solution using std::random_shuffle for heavy objects? 

Answer 1

Tạo một ngẫu nhiên hoán vị của dãy 0, 1, ..., N - 1 và chọn M đầu tiên của họ; sử dụng các chỉ số đó làm chỉ số vào vectơ ban đầu của bạn.

Một hoán vị ngẫu nhiên có thể dễ dàng thực hiện với các thư viện chuẩn bằng cách sử dụng std::iota cùng với std::random_shuffle:

std::vector<Heavy> v; // given 

std::vector<unsigned int> indices(V.size()); 
std::iota(indices.begin(), indices.end(), 0); 
std::random_shuffle(indices.begin(), indices.end()); 

// use V[indices[0]], V[indices[1]], ..., V[indices[M-1]] 

Bạn có thể cung cấp random_shuffle với một bộ tạo số ngẫu nhiên của sự lựa chọn của bạn; kiểm tra tài liệu ­ người đàn ông ­ để biết chi tiết.

Answer 2

Hầu hết thời gian, phương thức do Kerrek cung cấp là đủ. Nhưng nếu N là rất lớn, và M là đơn đặt hàng của độ lớn nhỏ hơn, phương pháp sau đây có thể được ưa thích.

Tạo một tập hợp các số nguyên chưa ký và thêm số ngẫu nhiên vào số đó trong phạm vi [0, N-1] cho đến khi kích thước của tập là M. Sau đó, sử dụng các phần tử tại các chỉ mục đó.

std::set<unsigned int> indices; 
while (indices.size() < M) 
    indices.insert(RandInt(0,N-1)); 

Answer 3

Vì bạn muốn nó có hiệu quả, tôi nghĩ bạn có thể nhận được một trả dần O(M), giả sử bạn có để thực hiện hoạt động đó rất nhiều lần. Tuy nhiên, cách tiếp cận này không phải là reentrant.

Trước hết hãy tạo một vector cục bộ (ví dụ: static) của std::vector<...>::size_type (ví dụ: unsigned sẽ làm) các giá trị.

Nếu bạn nhập chức năng của bạn, thay đổi kích thước vector để phù hợp với N và điền nó với giá trị từ kích thước cũ để N-1:

static std::vector<unsigned> indices; 
if (indices.size() < N) { 
    indices.reserve(N); 
    for (unsigned i = indices.size(); i < N; i++) { 
    indices.push_back(i); 
    } 
} 

Sau đó, chọn một cách ngẫu nhiên M con số duy nhất từ ​​vector rằng:

std::vector<unsigned> result; 
result.reserver(M); 
for (unsigned i = 0; i < M; i++) { 
    unsigned const r = getRandomNumber(0,N-i); // random number < N-i 
    result.push_back(indices[r]); 
    indices[r] = indices[N-i-1]; 
    indices[N-i-1] = r; 
} 

Bây giờ, kết quả của bạn đang ngồi trong vector result.

Tuy nhiên, bạn vẫn phải sửa chữa những thay đổi của bạn để indices cho các hoạt động tiếp theo, do đó indices là đơn điệu một lần nữa:

for (unsigned i = N-M; i < N; i++) { 
    // restore previously changed values 
    indices[indices[i]] = indices[i]; 
    indices[i] = i; 
} 

Nhưng phương pháp này chỉ hữu ích nếu bạn cần phải chạy thuật toán rằng rất nhiều và N không phát triển quá lớn đến mức bạn không thể sống với indices ăn RAM suốt.