Chọn các phần tử m một cách ngẫu nhiên từ một vector chứa các phần tử n

Question

Tôi có một vector chứa các phần tử n. Tôi cần chọn một tập hợp con gồm các phần tử m ngẫu nhiên từ vectơ mà không lặp lại. Cách hiệu quả nhất để làm điều này là gì? Tôi cần phải làm điều này vài nghìn lần trong mã của tôi.

Giải pháp trên đầu tôi là sử dụng rand() để tạo số ngẫu nhiên k giữa 0 và n. Sau đó chọn phần tử thứ k trong vectơ và chèn nó vào một std::set. Tiếp tục làm điều này cho đến khi kích thước của bộ này bằng m. Bây giờ tôi đã đảm bảo rằng tập hợp chứa m các yếu tố độc đáo được chọn ngẫu nhiên từ tập hợp các yếu tố n.

Các giải pháp khả thi khác là gì?

Cảm ơn.

Answer 1

Bạn muốn có một Fisher-Yates shuffle (dừng sau khi M lặp):

template<class BidiIter > 
BidiIter random_unique(BidiIter begin, BidiIter end, size_t num_random) { 
    size_t left = std::distance(begin, end); 
    while (num_random--) { 
     BidiIter r = begin; 
     std::advance(r, rand()%left); 
     std::swap(*begin, *r); 
     ++begin; 
     --left; 
    } 
    return begin; 
} 

Demo tại http://ideone.com/3A3cv. Tốc độ này nhanh hơn đáng kể so với std::random_shuffle khi bạn chỉ cần một vài số ngẫu nhiên trong tập hợp và sẽ chỉ ở cùng tốc độ ngay cả khi N==M.

Answer 2

Một cách để bạn có thể làm điều này là để tạo ra một danh sách tất cả các chỉ số của vector, shuffle họ, và lấy n đầu tiên được các chỉ số của các đối tượng được lựa chọn:

struct rangegenerator { 
    rangegenerator(int init) : start(init) { } 

    int operator()() { 
     return start++; 
    } 

    int start; 
}; 

vector<T> numbers; // this is filled somewhere else 

vector<int> indices(numbers.size()); 

generate(begin(indices), end(indices), rangegenerator(0)); 

random_shuffle(begin(indices), end(indices)); 

// then take the first n elements of indices and use them as indices into numbers