generating unsimilar random numbers

Pseudo-random sequences have repeats. It happens. That's why it's called random. If you really don't want repeats, just keep grabbing random numbers until you get one that's not a repeat. You don't need to come up with some uber pseudo random algo that doesn't repeat.

Quote:

Original post by jonahrowley some uber pseudo random algo that doesn't repeat

It's called "shuffling".

OK, with a range of 1 to 10, that would work. Not exactly practical for larger ranges though..

hey guys,
well first of thanks(learnt abt shuffling in your post).
but i was not really gunning for that.

i'm struggling with the coding aspect.

i was thinking on these lines...
1 .i generate a random sequence and store it into an array variable.
2.Then i need to iterate through them to see if there are repeats.
3.If there are i need to change those by running the random function again.

if you could hlp me out with the coe or piont me to someplace.
i've googled it and hit a few topics but i'd reckon some one must have run into similar situations here especially.

thanks again.
b

this way you are hading for a possible disaster.
what if it goes cycling ad infinitum(meaning you keep random-get already picked numbers.then your program stalls) the best possible worse scenario would be to have a long period of looping the random generator especially when the many numbers have been already picked(not infinity but very nightmarish)
OTOH you could choose a random number, see if it is already picked and iterate through the array in a normal fashion until you find one that hasn't already been picked up)
P.S.I must tell you what you mean is practically the same with shuffling, except you memorize an arbitrary length sequence(and do not perform real random the second time).What I have said is appliable to both
I suggest to run shuffling once and memorize some key points,if not the whole sequence

Something like this might have its uses. Play with the numbers and see what you find:

int limit = 10;for (int i = 0; i < limit; ++i){    cout << int(pow(7.0, i+1.0)) % (limit+1) << endl;}

1: Create an vector containing the numbers 1-10: myVector
2: Use a random number generator to create a 2 random numbers: i and j
3: std::swap(myVector[i % ( myVector.size()-1 )],myVector[j % ( myVector.size()-1 )]);
4: repeat steps 2-3 for a large number of iterations (relative to the length of the vector)
5: Now you have a random vector with no repeats.

Quote:

Original post by Nitage 1: Create an vector containing the numbers 1-10: myVector 2: Use a random number generator to create a 2 random numbers: i and j 3: std::swap(myVector[i % ( myVector.size()-1 )],myVector[j % ( myVector.size()-1 )]); 4: repeat steps 2-3 for a large number of iterations (relative to the length of the vector) 5: Now you have a random vector with no repeats.

replace steps 3 and 4 with std::random_shuffle(myVector.begin(),myVector.end()) for both better randomness and better performance.

Quote:

Original post by Trap Quote: Original post by Nitage 1: Create an vector containing the numbers 1-10: myVector 2: Use a random number generator to create a 2 random numbers: i and j 3: std::swap(myVector[i % ( myVector.size()-1 )],myVector[j % ( myVector.size()-1 )]); 4: repeat steps 2-3 for a large number of iterations (relative to the length of the vector) 5: Now you have a random vector with no repeats. replace steps 3 and 4 with std::random_shuffle(myVector.begin(),myVector.end()) for both better randomness and better performance.

And for less control if you want to tweak the algorithm... and less educational value seeing as he seems to want to know what's going on.

BTW, we've all assumed he's using C++ - might not be.

one possible solution is this:

1) make a cyclic linked list with 10 items (the numbers 1..10), representing the not picked list.
2) make an empty linked list, representing the picked list.

3) get a random number between 1 and Length-of-not-picked-list, iterate through not-picked list that number of times, take out the item there and insert it to the picked list. Repeat this step until not-picked-list is empty.


This way you can't stall the program and you get same possibiliy for every possible permutation (assuming good pseudo random numbers).

PS. you could use arrays or other containers instead of lists.

PS. yes, std::shuffle is better.

Iftah.

thanks so much folks,
i'm not that jiggy with c++ but that can be dealt with.
Nitage:Yeah thanks,i would any day like to know what's happenning over performance.

i'm actually using melscripting(maya) which is more in tune with C than c++ so i dont think i'll have the liberty to use either methods(shuffel or swap).but still good to know...thank you all.


b

Good thing to know about: AngleWyrm's hat container.

Regards,

Quote:

Original post by Nitage 1: Create an vector containing the numbers 1-10: myVector 2: Use a random number generator to create a 2 random numbers: i and j 3: std::swap(myVector[i % ( myVector.size()-1 )],myVector[j % ( myVector.size()-1 )]); 4: repeat steps 2-3 for a large number of iterations (relative to the length of the vector) 5: Now you have a random vector with no repeats.

Unfortunately, this algorithm yields very suboptimal results even with fairly large number of iterations. A better one, guaranteed to give a good shuffle in only length iterations is as follows (in pseudocode):

Given an n-length vector v with numbers [1, n]:

for i = 1 to n do  j = random number in range [1, n]  swap v, v[j]end

why don t you choose 2 different random number generators, that implement different algorithms to generate them and combine the results by .

op={*,/,+,-} and apply a modulo m where m is the upper limit of the interval of your random numbers


This will provide you random numbers that should be spread well over the interval with a pretty low probability of even/very similar numbers

You can t exclude similar numbers completely this way, but at least you don t speed such a lot of computation time on shuffling a array or iterating a list every function call.

Sharlin's got it.

1) Just fill an array sequentially with the numbers 1-10.
2) Iterate through the array, swapping element i with some random element j (could == i)

It's a 2n operation, and you're done.

My solution works in O(1)

for tiny intervals you can use a large one 0-10000 and scale the result down to an interval 0-n

What do you use this algorithm for? some sort of hashing? You just had to make the probability of similar random numbers in repeated function calls very very low

Basiror, I'm confused...

How are you proposing to randomly order N sequential integers in O(1) time? Maybe if you reword it I'll understand.

Quote:

Original post by Sharlin Given an n-length vector v with numbers [1, n]: for i = 1 to n do j = random number in range [1, n] swap v, v[j]end

You're almost there. But suppose you're shuffling an array of three elements. You choose 3 random numbers from 1 to 3, for a total of 27 possibilities. But there are 6 possible permutations of the array. 27 is not divisible by 6, so the algorithm cannot choose between the 6 permutations while making them all equally likely. Fortunately, you only need a tiny fix:

for i = 1 to n do  j = random number in range [1, i] // <-- changed  swap v, v[j]end

And you could start i from 2 at this point. (This is how some implementations of std::random_shuffle work.)

Quote:

Original post by smitty1276 Basiror, I'm confused... How are you proposing to randomly order N sequential integers in O(1) time? Maybe if you reword it I'll understand.

not at all,

I generate them with a pretty low probability for occurence of similar numbers.
The user wants to use them to create a scattering algorithm, so it shouldn t matter if there are equals, all that matters is that your generated random numbers don t concentrate in one point of your interval [0-n],in other words, they shall be spread evenly over the interval.

You can reduce the probability of similar numbers to be generated in repeated call by combining the results of several different random number generators and apply a modulo n (n is the upper bound of your interval)


and this works in O(1), you just solve a view equations and combine the results.

what you can do is to get rid of repeated numbers(which will be pretty rare) is to put your items with keys into a map and check if there s already a occurance if so you add/subtract "1" from the random number and check again. The lookup of the keys in the map work in O(logn).

Another solution is to count the number of objects you scattered, and use the count as the index of the next object you scatter.
Say you will scatter a maximum of 10000 objects for example:
num = random_number();
num=num*10000+count;
count++;

This way you still scatter the objects evenly over your interval and avoid repeated keys completely. Combined with the algorithm I suggested this works in O(1) and you don t have to hassle with lister iterations at all