अद्वितीय मानों के सेट से एक अद्वितीय यादृच्छिक सबसेट चुनें

Question

C++। विजुअल स्टूडियो 2010

मैं एक std::vector वी एन के अद्वितीय तत्वों (भारी structs) है। एम यादृच्छिक रूप से एम यादृच्छिक, अद्वितीय, तत्व कैसे चुन सकते हैं?

उदा। {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} और मैं तीन लेने ...

• 4, 0, 9
• 0, 7: वी 10 तत्व शामिल हैं , 8
• लेकिन यह नहीं: 0, 5, 5 < --- अद्वितीय नहीं!

एसटीएल को प्राथमिकता दी जाती है। तो, ऐसा कुछ?

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

रेंज 0, 1, ..., N - 1 के यादृच्छिक क्रमपरिवर्तन बनाएँ और उनमें से पहले M लेने; अपने मूल वेक्टर में सूचकांक के रूप में उनका उपयोग करें।

एक यादृच्छिक क्रमपरिवर्तन आसानी से std::iota एक साथ उपयोग करके मानक पुस्तकालय के साथ किया जाता है 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]] 

आप अपनी पसंद का एक यादृच्छिक संख्या जनरेटर के साथ random_shuffle आपूर्ति कर सकते हैं; विवरण के लिए docu ­ पुरुषों ­ टेशन देखें।

Answer 2

अधिकांश समय, केरेक द्वारा प्रदान की गई विधि पर्याप्त है। लेकिन अगर एन बहुत बड़ा है, और एम परिमाण की छोटी है, तो निम्न विधि को प्राथमिकता दी जा सकती है।

हस्ताक्षरित पूर्णांक का एक सेट बनाएं, और श्रेणी के आकार तक [0, एन -1] श्रेणी में यादृच्छिक संख्या जोड़ें। फिर उन अनुक्रमणिका में तत्वों का उपयोग करें।

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

Answer 3

जब से तुम यह कुशल बनना चाहता था, मुझे लगता है कि आप एक परिशोधित O(M) प्राप्त कर सकते हैं, यह मानते हुए आपको लगता है कि आपरेशन के समय का एक बहुत प्रदर्शन करने के लिए किया है। हालांकि, यह दृष्टिकोण पुनर्वित्त नहीं है।

सबसे पहले स्थानीय (यानी static) वेक्टर std::vector<...>::size_type (यानी unsigned करेंगे) मूल्य बनाते हैं।

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; 
} 

:

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

फिर, बेतरतीब ढंग से कि वेक्टर से M अद्वितीय संख्या लेने:

आप अपने समारोह दर्ज करते हैं, N से मेल खाते हैं और N-1 करने के लिए पुराने आकार से मूल्यों के साथ भरने के लिए वेक्टर आकार बदलने

अब, आपका परिणाम result वेक्टर में बैठा है।

हालांकि, अगर आप अभी भी अगले रन के लिए indices में अपने परिवर्तन की मरम्मत के लिए है ताकि indices फिर monotonic है:

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

लेकिन इस दृष्टिकोण ही उपयोगी है, तो आप उस एल्गोरिथ्म एक बहुत चलाने के लिए है, तो और N इतना बड़ा है कि आप ऊपर रैम हर समय खाने indices साथ नहीं रह सकते हो जाना नहीं है।