# Thread: List of numbers in random order

1. ## List of numbers in random order

How do you write the algorithm to generate a list of numbers from say 1-1000 but in random order? Do you have to use an array to keep track?

2. Do you know how to generate random numbers? Do you know how to use loops? Just seed the random number generator, and then create your random numbers inside a loop. If you want to avoid repeats, you can use an array and search that array each time a number comes up. If it's found, try again. If not, keep it and move on. You can refer to the FAQ for help on random numbers.

3. If it is in fact a list of numbers including every number between X and Y, then populate an array with them and shuffle it.

Quzah.

4. Originally Posted by quzah
If it is in fact a list of numbers including every number between X and Y, then populate an array with them and shuffle it.

Quzah.
How do you do this 'shuffling?'

5. How do you shuffle cards? ........ man, it's not brain surgery. Just jump around in the array and switch the places of variables until you get tired of doing it.

Quzah.

6. The most straight forward way is to use the random_shuffle() function defined in the algorithms header.

http://www.sgi.com/tech/stl/random_shuffle.html

EDIT: Damn, shouldn't code at night. Realized I was using the wrong header name and a non-standard extension function.
The following should work fine.

Code:
```#include <cstdlib>
#include <vector>
#include <algorithm>
#include <ctime>
#include <iostream>

using namespace std;

int main()
{
const size_t CONTAINER_SIZE = 1001;

srand( time(NULL) ); // seed rand
vector<int> nums(CONTAINER_SIZE);

for(size_t ix = 0; ix < nums.size(); ix++)    // fill from 1 to 1000
{
nums[ix] = ix + 1;
}

random_shuffle(nums.begin(), nums.end() );   // shuffle elements

for(size_t ix = 0; ix < nums.size(); ix++)
{
cout << nums[ix] << '\n';
}

return 0;
}```

7. Depending on the purpose of your project, it's also an interesting problem to solve.

I remember seeing one way to do it. To start you need a function like this:
size_t rand_in_range(size_t MAX_SIZE);
where MAX_SIZE represents the size of your array/container.

First pick a pick a position (like 0). Then generate a rand, go to that position, and swap the values of 0 and the random position. Then keeping track of the random position, generate a new random position, and swap again. Keep looping through as many times as you feel is necessary to get everything adequately shuffled.

8. You could do something like this
Code:
```     int *Cards = new int [1000];

for (int i=0; i<1000; i++)
{
int nextCard = rand()%1000;
Cards[i] = nextCard;
}```

9. to avoid repeats, you could also try:
Code:
```#include<iostream>
#include<cstdlib>
#include<ctime>

int main()
{
int cards&#091;1000&#093;;                //this array is to hold the random cards
unsigned short int taken&#091;1000&#093;; //this array is to keep track of used cards
srand(static_cast<unsigned int>(time(0))); //don't forget the seed

for(register int i=0;i<1000;i++)
taken&#091;i&#093;=0;                     //initialize the 'used' array

for(register int i=0;i<1000;i++)
{
int nextCard=1+rand()%1000;     //pull a random # in the range (1..1000)
if(taken&#091;nextCard-1&#093;==1)        //if the card's been used already
{
--i;                        //decrement the loop control variable
continue;                   //and start the loop from the top
}
cards&#091;i&#093;=nextCard;              //if not, use that card
taken&#091;nextCard-1&#093;=1;            //and mark it as used
}

for(register int i=0;i<1000;i++)    //output loop
std::cout<<cards&#091;i&#093;<<", ";

std::cin.get();
return 0;
}```
heh... got a little into it, so there's some working code...

10. That code might take a loooooooong time to execute. Think about it: once you're down to the last available card, each iteration has a 1/1000th chance of hitting it. In other words, the average runtime of this method is O(nē). Worst case - if rand() were truly random - would be forever, in the weird case that this last number just won't appear.

11. > Worst case - if rand() were truly random - would be forever,
Not so - true random numbers are allowed to repeat (just look at a coin toss).
Specifically excluding all previous results is not a random stream.

But yes, the solution is horrible - use a shuffle like Quzah suggested.

12. Originally Posted by Salem
> Worst case - if rand() were truly random - would be forever,
Not so - true random numbers are allowed to repeat (just look at a coin toss).
Specifically excluding all previous results is not a random stream.
Exactly what I'm saying. What if the random stream happens to repeat just one number for a year? It will always try to select the same card, thus looping and looping without ever getting anywhere.

rand() on the other hand is guaranteed to visit every number of its range once in a while.