1. ## More randomness

Hi, sorry if I'm asking a dumb question (having looked through the FAQ/boards etc), but here goes:

I need to generate a list of numbers from 1 (to a set number, for e.g. 25) in a random order. However, I can't have the same number twice, but I need the list ordering to be random.

ANy thoughts?

2. Have an array that will store the numbers, a variable that will tell you how many items are in the array, and a temporary variable that will hold the result of each random call.

Process would be:
1) call the random generator and put value into the temporary variable
2) Search the array (using the above mentioned variable to make sure you only look at values you've put in already).
3) If you didn't find a match, add in the temp and increase the size counter. Repeat until filled

3. Originally Posted by Thantos
Have an array that will store the numbers, a variable that will tell you how many items are in the array, and a temporary variable that will hold the result of each random call.

Process would be:
1) call the random generator and put value into the temporary variable
2) Search the array (using the above mentioned variable to make sure you only look at values you've put in already).
3) If you didn't find a match, add in the temp and increase the size counter. Repeat until filled
Search an array for each new random number? Even not taking into account duplicate values, this is a terribly inefficient process. IMO it's much better to just fill an array with the range of values and permute it randomly:
Code:
```#include <algorithm>
#include <cstdlib>
#include <iostream>

using namespace std;

double random();

int
main()
{
int *vals;
int  n;

cout<<"Upper limit: ";
if (!(cin>> n)) {
cerr<<"Input error"<<endl;
exit(EXIT_FAILURE);
}
// Make and fill array
vals = new int[n];
for (int i = 0; i < n; i++) {
vals[i] = i + 1;
}
// Random permutation
for (int i = 0; i < n - 1; i++) {
int x = static_cast<int>(random() * (n - i));
swap(vals[i], vals[i + x]);
}
// Prove that it works and clean up
for (int i = 0; i < n; i++) {
cout<< vals[i] <<endl;
}
delete [] vals;
}

double
random()
{
return static_cast<double>(std::rand()) / RAND_MAX;
}```

4. But what if you only wanted 20 numbers with a max value of 10000?

And I wasn't going for efficiently but ease of use and understanding for the questioner

5. >But what if you only wanted 20 numbers with a max value of 10000?
Then I would use a more suitable data structure than a simple array. But that wasn't the question. The question was a list of numbers from 1 to N in random order.
I need to generate a list of numbers from 1 (to a set number, for e.g. 25) in a random order.
>And I wasn't going for efficiently but ease of use and understanding for the questioner
I know, but I can't resist giving you a hard time every now and then. It keeps you on your toes.

6. I'm not sure why Preludes indicates that rand()/RAND_MAX is less likely to give a string of equal values on repeated values than rand()/modulus
Using the low order bits of a random number may not result in a good distribution. I've seen long strings of repeating numbers when using modulus with rand.
From what I see, Prelude is not talking about repeating values, but about the random distribution.
Her argument is that dividing by RAND_MAX conserves this distribution, while the modulo method often does not.

7. Originally Posted by weirdbeardmt
I need to generate a list of numbers from 1 (to a set number, for e.g. 25) in a random order. However, I can't have the same number twice, but I need the list ordering to be random.
The easiest way is this:

1. create the list storing 1..25, in order, in the indices 0..24
2. loop through the indicies, i = 0..24, pick a random index, j = 0..24, and swap the two.

This way, you swap a random index with each position, assuring that each index is swapped out at least once.

8. hmm... I did not see before posting that this thread was already several pages in length.
Anyway...

Any deterministic random number generator is predictable, i.e. rand().
Well, they are deterministic

There are devices which you can plug into your computer in order to generate non-deterministic random numbers.
Incidentally, Hotbits at fourmilab.ch provides such a generator, online.

For a pseudo-random number generator, I tend to use the Mersenne Twister, with a particular C++ implementation by Rick Wagner.

9. The problem with rand()%n using only the lower order bits is only a problem when n is a power of two.
Thus, the problem with rand()%n is not that much of a problem.

If you write rand()%3, the higher-order bits should also be taken into consideration.

Am I not correct, Prelude?

There are devices which you can plug into your computer in order to generate non-deterministic random numbers.
I have made an encryption program that uses noise from the microphone compressed with MD5 to generate keys of many megabits.
http://www.strandmark.com/otp.shtml

10. The problem with rand()%n using only the lower order bits is only a problem when n is a power of two.
Thus, the problem with rand()%n is not that much of a problem.

If you write rand()%3, the higher-order bits should also be taken into consideration.
I think that this is still a problem, since they arent always "taken into consideration" evenly.

11. >Am I not correct, Prelude?
Yes, the problem is most obvious when N is a power of 2.

12. Bah must have misread the question

I know, but I can't resist giving you a hard time every now and then. It keeps you on your toes
Sure pick an easy target (large feet)

13. What do you guys make of these nag routines which my dept. provides as a default install?

http://www.iss.soton.ac.uk/manuals/a...c/summary.html (about half way down for Random Number generators). I've used the equivalent in Fortran, but never in C...