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?
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?
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.
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.
Hope is the first step on the road to disappointment.
How do you do this 'shuffling?'Originally Posted by quzah
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.
Hope is the first step on the road to disappointment.
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; }
Last edited by AH_Tze; 02-08-2005 at 12:40 PM.
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.
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; }
to avoid repeats, you could also try:
heh... got a little into it, so there's some working code...Code:#include<iostream> #include<cstdlib> #include<ctime> int main() { int cards[1000]; //this array is to hold the random cards unsigned short int taken[1000]; //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[i]=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[nextCard-1]==1) //if the card's been used already { --i; //decrement the loop control variable continue; //and start the loop from the top } cards[i]=nextCard; //if not, use that card taken[nextCard-1]=1; //and mark it as used } for(register int i=0;i<1000;i++) //output loop std::cout<<cards[i]<<", "; std::cin.get(); return 0; }
Last edited by major_small; 02-08-2005 at 12:27 AM. Reason: logic errors in code...
Join is in our Unofficial Cprog IRC channel
Server: irc.phoenixradio.org
Channel: #Tech
Team Cprog Folding@Home: Team #43476
Download it Here
Detailed Stats Here
More Detailed Stats
52 Members so far, are YOU a member?
Current team score: 1223226 (ranked 374 of 45152)
The CBoard team is doing better than 99.16% of the other teams
Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)
Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT
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.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
> 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.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
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.Originally Posted by Salem
rand() on the other hand is guaranteed to visit every number of its range once in a while.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law