generate list of random numbers without dup

[littlepig]

I want to find any plain and efficient way, thanks.

[TheIdeasMan]

Ok, what have you tried so far? If you don't have code, even some thoughts how to do it?

[littlepig]

#ifndef DICE_H_
#define DICE_H_
#include <vector>
#include <algorithm>
#include <numeric>
using std::vector;

class Dice{
public:
	Dice(const vector<int> &hit_rates);
	~Dice(){}


	int Roll(const vector<int> &ignored_indexes);

	int Roll();


	bool MultiRoll(unsigned int num, vector<int> *pvDest) ;
private:
	const vector<int> *m_pvHitRate;
	const int m_iTotalSum;


};
#endif 

Dice::Dice(const vector<int> &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<int> &ignored_indexes) {
	unsigned int i;
	int current_sum = 0;
	int total_sum = m_iTotalSum;
	for (vector<int>::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<int> ignored_indexes;
	return Roll(ignored_indexes);
}
bool Dice::MultiRoll(unsigned int num, vector<int> *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

#include <iostream>
#include "Dice.h"
#include <ctime>
#include <iterator>
#include <algorithm>
using namespace std;

int main(){
	const int Range = 30000;
	vector<int> hit_rate(Range,1);
	vector<int> 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<int, char> 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?

[TheIdeasMan]

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

[kbw]

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.

[JLBorges]

#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
#include <cstdlib>
#include <ctime>
#include <iostream>

// generate n unique random numbers in ( 0, m )
// O(m) time, O(m) space
std::vector<int> generate_unique_rand_1( std::size_t n, std::size_t m )
{
    assert( n < (m+1) ) ;
    std::vector<int> 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<int> generate_unique_rand_2( std::size_t n, std::size_t m )
{
    assert( n < (m+1) ) ;
    std::vector<int> 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' ;
}