Random numbers

This topic is 4261 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'd like to generate a series of numbers between 1 and 10. That's no problem. However, I'd like to make sure I don't get the same number twice in a row. I considered doing a while loop like: number1 = rand(); number2 = rand(); while (number2 == number1) { number2 = rand(); } The problem I foresee with this method is that, theoretically, it could run forever. And although it problably won't it may cause my program to hang up for a short time. Can anyone think of a way to not get the same number twice or what I could do with that number if it arises a second time. Thanks, Thomo.

Share on other sites
When generating random numbers from a to b there is always a 1/(b-a+1) chance of repeating any given number. The only solution to this is to test for equality and discard if the numbers are unequal. Potentially, this could run for quite a while, however it is highly unlikely. The probability of choosing a number, and then choosing that same number again is 1/10, three times is 1/100, four times 1/1000. Unless you are doing this quite a bit (generating hundreds of thousands of random numbers) you are unlikely to see any runs of more than 5 or 6 in a row. Making seven successive calls to rand() is not terribly slow and I wouldn't think it would cause your program to hang.

Share on other sites
If you absolutely have to avoid it, you can generate a random number from 1 to 9 and add one if it's greater than or equal to the previous number.

Share on other sites
Thanks.

I'll see how the first situation fairs up. I agree that it probably won't take too many iterations to get a differen number. I after testing my program there is a problem I'll try the second.

Share on other sites
What you could do is rather than repeatedly try to generate the numbers 1 to 10 in a random order, you could create a list of numbers 1 to 10 and shuffle them randomly, that way you can guarentee that it wouldn't loop for ever.

Just an idea ;-)

Share on other sites
Quote:
 Original post by Beer HunterIf you absolutely have to avoid it, you can generate a random number from 1 to 9 and add one if it's greater than or equal to the previous number.

Of course, you get an uneven distribution of probability with that approach, because you're now twice as likely to get the number one more than the previous one, which may or may not be suitable to the application.

Thomo: I've used that particular technique you included in your inital post myself many times, and have never noticed any delays from its use. As jperlata wrote, it's so unlikely you'll get more than ten "retries" from your random number generator that it's not worth worrying about. I'm sure it will be fine!

Share on other sites
Quote:
 Original post by xstreme2000What you could do is rather than repeatedly try to generate the numbers 1 to 10 in a random order, you could create a list of numbers 1 to 10 and shuffle them randomly, that way you can guarentee that it wouldn't loop for ever.Just an idea ;-)
Is there not some function like std::random_shuffle?

Share on other sites

Create an array of size of 10. Then fill your array with numbers 1-10.

Then take two random numbers in range [0,9] and swap those array entries together. Repeat the steps several times.

- Doesn't require any checking and scales up pretty well.

Cheers

Share on other sites
Quote:
Original post by Evil Steve
Quote:
 Original post by xstreme2000What you could do is rather than repeatedly try to generate the numbers 1 to 10 in a random order, you could create a list of numbers 1 to 10 and shuffle them randomly, that way you can guarentee that it wouldn't loop for ever.Just an idea ;-)
Is there not some function like std::random_shuffle?

Yes, I do believe there is ;-)

Share on other sites
Someone posted exactly the same question just a few days ago (well, 1-6 instead of 1-10). Here is the thread: Random Selection Problem

Take a look at janta's reply. It is the best solution and it hasn't been mentioned here yet.

Share on other sites
Quote:
Original post by Trapper Zoid
Quote:
 Original post by Beer HunterIf you absolutely have to avoid it, you can generate a random number from 1 to 9 and add one if it's greater than or equal to the previous number.
Of course, you get an uneven distribution of probability with that approach, because you're now twice as likely to get the number one more than the previous one, which may or may not be suitable to the application.
Nonsense! The nine possible choices all have a 1/9 chance of being selected.

Also, everyone: random_shuffle is not the answer. We just want to avoid getting the same number twice in a row! We're supposed to allow sequences like 1, 2, 5, 1, 7, 1, 9, 1, 9, 1, 9, 1 as output.

Share on other sites
To select two things from a single set, without duplicates and with even distribution you need to call rand with 2 different arguments like that: rand_up_to(num) and rand_up_to(num-1) (though that alone doesn't guarantee correct results)

random_shuffle does that and Beer Hunters method does it to. I'd use the method proposed by Beer Hunter, it's correct, fast and easy to implement.

It can be interpreted as a 2 step knuth shuffle, you first select the element you picked last and pick one of the remaining elements. Excluding the last one picked would be done by swapping with the first or last element in random_shuffle, in the method by Beer Hunter it's done by logically deleting the last one picked and left-shifting all remaining elements.

Like that:
123456 -- numbers to pick from  x    -- number picked12456  -- remaining numbers

Share on other sites
I'm not sure how long the data returned by rand() is, but I imagine that statistically once every 2^32 cycles having a single extra loop is pretty much 'no problem'.

Share on other sites
Quote:
 Original post by The ParrotI'm not sure how long the data returned by rand() is, but I imagine that statistically once every 2^32 cycles having a single extra loop is pretty much 'no problem'.
If your rand implementation is that bad, it's best avoided as a PRNG.

Share on other sites
"Statistically" :) if you ran it for semi-eternity, statistically it'd occur every 2^32, if it returns a 32-bit number.

Share on other sites
I usually regret replying when I haven't read all the replies, but this solution may give you good results.

-Create an array containing the integers 1 through 10 (or 9, or whatever numbers you want...it doesn't matter).

-Get a random number from 0 to 8 (or 9, are you looking for an integer between 0 and 9? 1 and 10? I can't remember). Use this number as the index of the returned "random" number. Then swap the index with the last index (which is past the range of the random number).

-Of course the first time this is executed you may need to handle it specially since you'll want to be able to randomly get any of the numbers, but that's not that complicated.

As an example you'd have:

1,2,3,4,5,6,7,8,9,10

-> Generate random number between 0 and 9 (since this is the first execution). You get 3.

Swap index 3 with index 9 and return index 9

1,2,3,10,5,6,7,8,9,->4<

Share on other sites
Quote:
 Original post by JohnBoltonSomeone posted exactly the same question just a few days ago (well, 1-6 instead of 1-10). Here is the thread: Random Selection ProblemTake a look at janta's reply. It is the best solution and it hasn't been mentioned here yet.

janta's solution makes the most sense. Now instead of randomizing it to N-k, you randomize it to N-1. Have an array of N elements, pick one, swap it with the last element, then pick one from N-1 elements, swap it, lather rinse and repeat.

Share on other sites

Very simple. N=10

make an array with elements range 0...N-1 (note array elemen starts 0)

fill in the numbers 1 ... 10 into each corresponding array element

NOW to pick a sequence of numbers (with no repeets) with NO infinite looping problem:

generate a random number R value 0 .. N-1

take the output value from that element [R]

slide all the elements following it down one slot (so that they are all now in elements 0..N-2) ex if R was 3 array will contain 1 2 3 5 6 7 8 9 10

Downcount N

you can now repeat for the next number in the sequence (upto 10 picks total)

Note- you have endcases when R == N-1 (there are none above to slide down)
and when N=1 the array element [0] will be the only remaining number

Share on other sites
This thread has turned into a gigantic WTF. People keep re-posting the same overcomplicated approaches -- even the ones that don't solve the problem at hand! The best solutions thus far were given in the first two replies.

Share on other sites
Quote:
Original post by Beer Hunter
Quote:
Original post by Trapper Zoid
Quote:
 Original post by Beer HunterIf you absolutely have to avoid it, you can generate a random number from 1 to 9 and add one if it's greater than or equal to the previous number.
Of course, you get an uneven distribution of probability with that approach, because you're now twice as likely to get the number one more than the previous one, which may or may not be suitable to the application.
Nonsense! The nine possible choices all have a 1/9 chance of being selected.

Ah, you're right. I misread your algorithm as just adding one when the random number is equal to the previous number.

And I also agree that the solutions here are starting to get way over the top [grin].

Share on other sites
Here is my solution. No internal array so it should scale well with larger ranges. A single var is used, and should be fast - just a conditonal testing and a assignment. It also perserves the distrubtion quality of the built in rand funtion mathmatically.

Note: the End range is one past of what you want. 0,10 would have range of 0-9

#include <iostream>#include <cstdlib>#include <ctime>#include <algorithm>#include <vector>#include <boost/static_assert.hpp>template<typename ValueType, ValueType Start, ValueType End >class rand_number_norepeat{private:	BOOST_STATIC_ASSERT(End-Start >= 2);public:	rand_number_norepeat() : last_used(rand() % (End-Start-1) + Start) {}		ValueType operator() (void)	{		ValueType i = (rand() % (End-Start-1) + Start);		if(i >= last_used)	++i;		last_used = i;		return i;	}private:	ValueType last_used;};int main(){	srand((unsigned)time(NULL));	rand_number_norepeat<std::size_t, 0, 10> a;	std::vector<std::size_t> vec(1000000);	std::generate(vec.begin(), vec.end(), a);	std::cout << "Testing 1 million numbers please wait" << std::endl;	std::vector<std::size_t>::iterator i =		std::adjacent_find(vec.begin(), vec.end());	if(i == vec.end())		std::cout << "no sequential repeating numbers found - 1 million numbers tested \n";	else		std::cout << "a sequential repeating number has been found.\n Test of 1 million random numbers :(\n";	return 0;}

Edit: Beer Hunter posted this approach right away. I miss read his reply eariler and thought it wouldnt perserve distrubtion :)

Share on other sites
I think I have a proper solution that requires no array-

// this function returns a random number 1..10 and doesnt repeat the same number twice in a rowint getNextNumber(){  static int lastNumber = 1;  int a = lastNumber-1;  // convert to 0..9 range  a = a + random(1..9);  // a is now 1..18 range  a = a % 10;            // a is now 0..9 range again,                         // note "a" cant be same as before,                          // as that requires adding a 0 or 10 (or 20 or 30...)  lastNumber = a+1;      // range 1..10  return lastNumber;}

the logic is simple - add 1..range-1 and use modulo to wrap around.

edit: this code above the first number will never be 1 as "lastNumber" is initialized to 1, you can initialize it to random number to be more fair to the first function call.

Iftah.

[Edited by - Iftah on June 27, 2006 3:05:40 AM]

Share on other sites
Unless you are doing something really weird, can't a simpler solution work?
number1 = rand();number2 = (number1 + rand()) % RAND_MAX;

Anyway, your first solution is a correct one: on most implementation, rand() computes number n+1 using number n. For example, VC7 implementation is using this formula:
holdrand = holdrand * 214013L + 2531011L
(Plus some other micro tweaks, but the value of holdrand is stored at this point)
If rand<inf>n+1</inf> = rand<inf>n</inf> and rand<inf>n+2</inf> = rand<inf>n+1</inf> and rand<inf>n+3</inf> = rand<inf>n+2</inf> then you probably have a constant value of holdrand (or the internal data that store the previous base value for rand(). And I guess that no implementation of rand() is plagued with such a problem. If your implementation is, then your loop will last forever, and the only way to change this is to srand() again. Thus, your code is likely to be
number1 = rand();number2 = rand();while (number1 == number2) {  srand(time(NULL));  number2 = rand();}

You then loose the ability to reproduce a particular sequence of number1/number2, but that's not usually a big problem.

Note that I didn't say that you can't get twice the same value. For example, MS implementation performs the following operations:
holdrand = holdrand * 214013L + 2531011L;return (holdrand >> 16) & 0x7fff; // RAND_MAX is 32768

The shift and the modulo may produce identical values for different values of holdrand - but in the end, if holdrand is changing then the return value of rand() will change - and your loop will not last forever.

HTH,

Share on other sites
Emmanuel, in your solution number2 can be same as number1 if rand returns 0, and he required it not to be so (he also required it to be in 1..10 range).

Also, there is no need to re-seed, every random implementation the numbers were chosen to never allow the generator to get "stuck" on the same number. You should (almost) never seed more than once.

Also re-seeding in the while loop is a big NO NO and a very bad advice.
On some (most?) compilers srand(time()) takes the current seconds as seed, which will mean that the loop will get stuck for a whole second, and on some probability for more than one second.

For example suppose seeding to time 1275 will result num2==num1, then the loop will get stuck until the time change to 1276 (say a billion iterations), and if by probability seeding to 1276 will also result num2==num1 you get stuck for an entire second again...

Share on other sites
In javascript I achieved a random shuffle by first assinging a random number to for each element in an array of objects, and then sorting the by their assigned value. Although javascript's random number generator sucks, my method did a decent job of shuffling.

I just thought of another more efficient way to randomly shuffle.

1) Keep a int of how many values are left - ie int count=list.length();
2) Randomly select an element from the container within the range of the number of values remaining - ie select from elements 0 through count -1
3) Use that element and then swap it with the element at the end of the list, then decrease the values remaining count by one.
4) Repeate 1-3 and when you have 0 remaining you have shuffled through all.

This probably is more complex than your problem however.

[Edited by - T1Oracle on June 27, 2006 4:11:28 AM]