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;
}

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.

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.

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.

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.

Originally Posted by laserlight

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)

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++;

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.

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.

Originally Posted by iMalc

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;
}

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.

Originally Posted by iMalc

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.)

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).

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

Originally Posted by manasij7479

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.