### generate list of random numbers without dup

I want to find any plain and efficient way, thanks.
Ok, what have you tried so far? If you don't have code, even some thoughts how to do it?
 ``1234567891011121314151617181920212223242526`` ``````#ifndef DICE_H_ #define DICE_H_ #include #include #include using std::vector; class Dice{ public: Dice(const vector &hit_rates); ~Dice(){} int Roll(const vector &ignored_indexes); int Roll(); bool MultiRoll(unsigned int num, vector *pvDest) ; private: const vector *m_pvHitRate; const int m_iTotalSum; }; #endif ``````

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950`` ``````Dice::Dice(const vector &hit_rates) : m_pvHitRate(&hit_rates), m_iTotalSum(std::accumulate(hit_rates.begin(), hit_rates.end(), 0)) { srand(time(NULL)); } int Dice::Roll(const vector &ignored_indexes) { unsigned int i; int current_sum = 0; int total_sum = m_iTotalSum; for (vector::const_iterator it = ignored_indexes.begin(); it != ignored_indexes.end(); it++) total_sum -= m_pvHitRate->at(*it); int target_sum = rand() % total_sum; for (i = 0; i < m_pvHitRate->size(); i++) { if (find(ignored_indexes.begin(), ignored_indexes.end(), i) != ignored_indexes.end()) { //found in ignored_indexes continue; } current_sum += m_pvHitRate->at(i); if (current_sum > target_sum) { //reached the target_sum, return the index break; } } return i; } int Dice::Roll() { vector ignored_indexes; return Roll(ignored_indexes); } bool Dice::MultiRoll(unsigned int num, vector *pvDest) { pvDest->clear(); if (num > m_pvHitRate->size()) { return false; } unsigned int cur_num = 0; while (cur_num < num) { //try to roll a single number int res = Roll(*pvDest); pvDest->push_back(res); cur_num++; } return true; }``````

this is my solution which using the hit rate as class property. but when I faced a bottle neck when range up to 30000
 ``123456789101112131415161718192021222324252627282930313233343536`` ``````#include #include "Dice.h" #include #include #include using namespace std; int main(){ const int Range = 30000; vector hit_rate(Range,1); vector result; Dice dc(hit_rate); time_t cp3 = time(NULL); cout << "Roll test:" << endl; for (int i = 0 ; i < Range ; i++){ cout << dc.Roll() << "\t"; } cout << endl; time_t cp4 = time(NULL); cout << "time used: " << cp4 - cp3 << endl; cout << "MultiRoll test:" << endl; bool rtv = dc.MultiRoll(Range/2, &result); time_t cp5 = time(NULL); ostream_iterator out(cout, "\t"); if (rtv == false) cout << "multiroll failed"; else copy(result.begin(), result.end(), out); cout << endl; cout << "time used: " << cp5 - cp4; }``````

Can anyone help me?
OK, what about the unique algorithm? This could be more efficient than only push_back if it's not already there approach, for relatively large number of unique values. That way the unique algorithm cycles through the vector once rather than through the whole vector every time.

If the vector of unique values is relatively very small and the whole list is very large, then find might be better. If the unique values is say 20 and the whole list is say factorial something.

HTH
You should only seed the PRNG once, so don't do it in a constructor.

I couldn't quite work out what you're doing, it seems awfully complicated. It wasn't obvious to me why the class had a pointer to a container.

You could use a sorted container (like set) to store values. If you need to preserve order, you can store values in a non-sorted container and only insert into that if the sorted container does not already have the value.
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950`` ``````#include #include #include #include #include #include #include // generate n unique random numbers in ( 0, m ) // O(m) time, O(m) space std::vector generate_unique_rand_1( std::size_t n, std::size_t m ) { assert( n < (m+1) ) ; std::vector seq(m+1) ; std::iota( seq.begin(), seq.end(), 0 ) ; std::random_shuffle( seq.begin(), seq.end() ) ; seq.resize(n) ; return seq ; } // generate n unique random numbers in ( 0, m ) - m much larger than n // O(m) time, O(n) space std::vector generate_unique_rand_2( std::size_t n, std::size_t m ) { assert( n < (m+1) ) ; std::vector seq ; std::size_t selected = 0 ; for( int i = 0 ; selected < n ; ++i ) { if( ( std::rand() % (m+1-i) ) < (n-selected) ) { seq.push_back(i) ; ++selected ; } } std::random_shuffle( seq.begin(), seq.end() ) ; return seq ; } int main() { std::srand( std::time(nullptr) ) ; for( int i : generate_unique_rand_1(10,99) ) std::cout << i << ' ' ; std::cout << '\n' ; for( int i : generate_unique_rand_2(10,999999) ) std::cout << i << ' ' ; std::cout << '\n' ; }``````
Topic archived. No new replies allowed.