List of numbers in random order

This is a discussion on List of numbers in random order within the C++ Programming forums, part of the General Programming Boards category; How do you write the algorithm to generate a list of numbers from say 1-1000 but in random order? Do ...

  1. #1
    Registered User
    Join Date
    May 2003
    Posts
    195

    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. #2
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    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. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    195
    Quote 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. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.

  6. #6
    Registered User
    Join Date
    May 2003
    Posts
    82
    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 11:40 AM.

  7. #7
    Registered User
    Join Date
    May 2003
    Posts
    82
    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. #8
    Banned
    Join Date
    Oct 2004
    Posts
    250
    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. #9
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    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...
    Last edited by major_small; 02-07-2005 at 11:27 PM. 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

  10. #10
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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

  11. #11
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,592
    > 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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote 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.
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-20-2009, 11:37 PM
  2. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 05:55 PM
  3. random numbers
    By mesmer in forum C Programming
    Replies: 4
    Last Post: 10-24-2008, 01:22 PM
  4. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21