Like Tree3Likes
  • 1 Post By laserlight
  • 2 Post By iMalc

Non-Repeating Random Number help

This is a discussion on Non-Repeating Random Number help within the C++ Programming forums, part of the General Programming Boards category; I need some help creating a rand number that will not come up with a number that has already been ...

  1. #1
    Registered User
    Join Date
    Aug 2012
    Posts
    2

    Non-Repeating Random Number help

    I need some help creating a rand number that will not come up with a number that has already been called. For example, a tic-tac-toe game which allows a player to play against a computer. This code will limit the numbers from 1-9, but they still repeat.

    Code:
    #include <iostream>
    #include <cstdlib>
    #include <time.h>
    const int LOW = 1;
    const int HIGH = 9;
    
    using namespace std;
    
    int main()
    {
    int comp_choice;
    time_t seconds;
    time(&seconds);
    srand((unsigned int) seconds);
    comp_choice = rand() % (HIGH - LOW + 1) + LOW;
    cout<<"the computer picked: "<<comp_choice;
    return 0;
    }
    

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Glyfada,Athens
    Posts
    2,650
    A stupidē way is to keep history of the random numbers that are already have been evaluated.Then if
    Code:
    rand() % (HIGH - LOW + 1) + LOW;
    returns you the on of the numbers that already have been called,then evaluate again,until a new one is called.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    Quote Originally Posted by Thehicks13
    A stupidē way is to keep history of the random numbers that are already have been evaluated.
    In this case, that is not stupid at all: the program will presumably keep track of the positions in the grid that have already been filled out.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    If they are in the range as small as 1-9, I think a better way is:
    Code:
        std::vector<int> y = {1,2,3,4,5,6,7,8,9};
        std::random_shuffle(y.begin(),y.end());
    After that, you can get elements from that vector in order whenever you need a random number.
    After 9 times, use std::random_shuffle again and start from the beginning.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    Quote Originally Posted by manasij7479
    After that, you can get elements from that vector in order whenever you need a random number.
    Not quite, because the opponent plays the game too, so the next number may not be available if the opponent has picked it in a prior move.
    manasij7479 likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    Quote Originally Posted by laserlight View Post
    Not quite, because the opponent plays the game too, so the next number may not be available if the opponent has picked it in a prior move.
    Missed that !
    So... the original way should be only way....or can some data structure be used for this to determine without searching or trial and errors ? (Ignore the small range)
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    A scheme like this could work. Storage in the nums array could be as little as one bit per number in the range, but here I've used an entire int.
    Code:
    const int SIZE = 9;
    
    int nums[SIZE] = {0}; // 0 means unused; 1 means used.
    int nums_used = 0;  // no more numbers when nums_used == SIZE
    
    
    // When player picks a number:
    nums[player_choice] = 1;
    nums_used++;
    
    
    // When computer picks a number:
    int i = rand() % SIZE;
    while (nums[i]) // If i already used, find next unused.
        i = (i + 1) % SIZE;
    nums[i] = 1;
    nums_used++;
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,403
    You could use the shuffle vector example and replace the value with a flag like 100 once it has been chosen - you then just ned to repopulate the vector for a new game then shuffle and play again.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    If the number that it picked randomly was already chosen by the user, then just pick again.
    In fact, that pretty much applies to whichever technique you you here too.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by iMalc View Post
    If the number that it picked randomly was already chosen by the user, then just pick again.
    In fact, that pretty much applies to whichever technique you you here too.
    I tried to design the idea in post 7 to not "just pick again", at least in the sense of generating another random number. The random number picks a random position in the "used numbers" (aka nums) array. If that number is used it searches for the first unused number.

    However, I have a sneaking suspicion that the scheme is not completely random.

    Code:
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    
    const int SIZE = 9;
    
    void test_rnd() {
        int nums[SIZE] = {0};
        for (int nums_used = 0; nums_used < SIZE; nums_used++) {
            int i = rand() % SIZE;
            while (nums[i]) i = (i + 1) % SIZE;
            nums[i] = 1;
            std::cout << i << ' ';
        }
        std::cout << '\n';
    }
    
    int main() {
        srand(time(0));
        for (int i = 0; i < 10; i++)
            test_rnd();
        return 0;
    }
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    Correct, that will be biased towards picking an item that follows a group of already chosen items.

    I was thinking along the lines of what manasij7479 had:
    Code:
        // Set up
        std::vector<int> y = {1,2,3,4,5,6,7,8,9};
        std::random_shuffle(y.begin(),y.end());
    
    
        // Execute this code to do the picking each time:
        int choice = 0;
        while (!y.empty())
        {
            choice = y.back();
            y.pop_back();
            if (!TakenByPlayer(choice))
                break;
        }
    It was the right idea as it scales to much larger datasets the best, he just panicked when the idea was challenged, rather than altering and defending the idea.
    Last edited by iMalc; 08-27-2012 at 03:11 AM.
    rogster001 and laserlight like this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,490
    Quote Originally Posted by iMalc View Post
    Code:
        // Set up
        std::vector<int> y = {1,2,3,4,5,6,7,8,9};
        std::random_shuffle(y.begin(),y.end());
    
    
        // Execute this code to do the picking each time:
        int choice = 0;
        while (!y.empty())
        {
            choice = y.back();
            y.pop_back();
            if (!TakenByPlayer(choice))
                break;
        }
    Doesn't that line nullify all advantages of this approach ?
    Well, the best way I can think of implementing that function is binary search but that would require a sorting after each turn.
    (And is what I meant by trial and error in the 'panic' (!) reply.)
    Last edited by manasij7479; 08-27-2012 at 04:09 AM.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    Quote Originally Posted by manasij7479
    Doesn't that line nullify any advantage of this approach ?
    It is a bit of a bummer, but it does have the advantage in that you don't risk having to keep generating a random number because it has already been taken when you have a large list of numbers and only a few valid choices left (which is the advantage of shuffling over re-trying in the first place).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    3,803
    Doesn't that line nullify all advantages of this approach ?
    How?

    Seriously, before you read further, how does needing an operation to confirm an empty slot nullify the advantages of a correctly randomized guess queue?

    Well, the best way I can think of implementing that function is binary search but that would require a sorting after each turn.
    You are apparently too close to the problem.

    Before reading further, consider the problem outside of this context. You have an set of slots that can be randomly accessed in constant time and need to know if a specifically chosen slot is free for use? Do you still perceive that as a binary search?

    Determining if a slot has been used is a constant operation in that context.

    Let's replace the implied function with a simple bit of code and add the slot array. (I adapted this "in place" from the code posted by iMalc; beware of bad formatting, weird offers, and typos.)

    Code:
        // Set up
        unsigned int b[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        std::vector<int> y = {1,2,3,4,5,6,7,8,9};
        std::random_shuffle(y.begin(),y.end());
        int g(0);
        int c = 0;
        // reinit
        std::random_shuffle(y.begin(),y.end());
        g = 0;
        for(int i(1); i < 10; ++i)
        {
            b[i] = 0;
        }
        // Execute this code to do the picking each time:
        do {
            c = y[g++];
        } while(b[c] != 0);
        b[c] = 1;
    Soma

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    Quote Originally Posted by manasij7479 View Post
    Doesn't that line nullify all advantages of this approach ?
    What it actually does is makes the time taken to pick the next spot amortised O(1) time, (like push_back on a vector). Most of the time there will be only 1 or 2 times through the loop.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Non-repeating random numbers
    By rachel7430 in forum C++ Programming
    Replies: 15
    Last Post: 08-03-2009, 09:01 AM
  2. Replies: 17
    Last Post: 06-06-2008, 04:47 AM
  3. non-repeating random numbers
    By redx2evil in forum C Programming
    Replies: 10
    Last Post: 10-29-2006, 04:25 PM
  4. Finding a repeating number in an array?
    By kabuatama in forum C Programming
    Replies: 7
    Last Post: 03-08-2006, 02:25 PM
  5. non repeating random number generation?
    By gencor45 in forum C# Programming
    Replies: 1
    Last Post: 02-08-2005, 04:23 PM

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