Generating random numbers WITHOUT duplicates

This is a discussion on Generating random numbers WITHOUT duplicates within the C++ Programming forums, part of the General Programming Boards category; How can I generate random numbers without duplicates assuming I have a function that will generate random integers from x ...

  1. #1
    fake1
    Guest

    Generating random numbers WITHOUT duplicates

    How can I generate random numbers without duplicates assuming I have a function that will generate random integers from x to y inclusive.

    Thanks.

  2. #2
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    Keep a record of all previous random numbers and reject any new random numbers that match one of these.

  3. #3
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    To add to what sorenson said. A binary tree will allow you to do this quickly. Call rand in a loop and pass the output to your binary tree insert func which you have coded to reject duplicates. End the loop when the tree contains the right number of values. You could also use stl set or stl map to do this if that sounds like too much work for you.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  4. #4
    Budding Synth Programmer samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Trefforest
    Posts
    368
    If you can't be arsed to code a binary tree class then: if you know how many numbers you need, create an array of that size and fill it with 1, 2, 3... and swap random pairs a few thousand times (trivial for a PC). For more variety instead of having each slot one greater than the last make it a random amount bigger. Like:

    Code:
    void swap (int *one, int *two);
    
    void main (void)
    {
       int i;
    
       int num [20];
       int newNum = 1;
    
       int swapOne;
       int swapTwo;
       
       for (i = 0; i < 20; i++)
       {
          num [i] = newNum;
          newNum += (random (5));
       }
    
       for (i = 0; i < 9000; i++)
       {
          swapOne = random (20);
    
          do
          {
              swapTwo = random (20); 
          } while (swapTwo == swapOne);   // Avoid duplicates.
    
          swap (num + swapOne, num + swapTwo);   // Or use &num [swapOne], etc.
       }
    }
    
    void swap (int *one, int *two)
    {
       int temp = *one;
    
       *one = *two;
       *two = temp;
    }
    If you have no random () function (like MSVC). The definition is as follows:

    Code:
    int random (int r)
    {
       return (rand () % r);
    }
    Last edited by samGwilliam; 02-09-2002 at 07:17 PM.
    MSVC++ 6.0

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Generating random letters
    By ominub in forum C Programming
    Replies: 6
    Last Post: 04-29-2009, 01:12 AM
  2. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 01:02 PM
  3. Random Number Generating
    By K.n.i.g.h.t in forum C Programming
    Replies: 9
    Last Post: 01-30-2005, 01:16 PM
  4. Another brain block... Random Numbers
    By DanFraser in forum C# Programming
    Replies: 2
    Last Post: 01-23-2005, 04:51 PM
  5. generating random numbers within a range
    By tucky in forum C Programming
    Replies: 3
    Last Post: 09-14-2001, 12:59 PM

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