How to Generate Random Numbers in C++ Without Repetition
#1 Guest_Rlhh*
Generating a random number without repetition
Posted 23 April 2010 - 06:38 PM
I'm trying to print an array of 3x3 and placing random numbers within them that has no repetition. I think what I did was right but repetition still occurs. Does anyone have any idea what is wrong?
#include <stdio.h> #include <stdlib.h> #include <time.h> int main(void) { int i,j,k,l; //loop initilizers int count =-1; //to check for repetition int num; int grid[3][3] = {}; srand(time(NULL)); //generating the array & checking for repetition for(i=0;i<3;i++) { for(j=0;j<3;j++) { num = 1 + rand()%9; grid[i][j] = num; for(k=0;k<3;k++) { for(l=0;l<3;l++) //checking the column for repetition { if(grid[k][l]==num) count++; } } if(count<=0) { //if number isn't found in either row or column, grid[i][j]=num; //set the number into array count = -1; } else { printf("repeated number = %d\n",num); grid[i][j]=-1; count = -1; } } } for(i=0; i<3; i++) //printing the array { for(j=0; j<3; j++) printf("%d ", grid[i][j]); } return 0; } Is This A Good Question/Topic? 0
#2 poncho4all 
Reputation: 123
- Posts: 1,422
- Joined: 15-July 09
Re: Generating a random number without repetition
Posted 23 April 2010 - 06:50 PM
i dont know but wouldn't it be easier to fill an array with all 9 numbers and then check for repetition and add another random number till no numbers are alike and then putting them in the 3x3 array?
Just a thought maybe i see it different 
#3 CTphpnwb
Reputation: 3872
- Posts: 14,201
- Joined: 08-August 08
Re: Generating a random number without repetition
Posted 23 April 2010 - 07:47 PM
Better to fill the grid with the numbers you want and then scramble them:
#include <iostream> using namespace std; const int arraySize = 3; int grid[arraySize][arraySize]; void initarrays( int ar[arraySize][arraySize]); void scramble( int ar[arraySize][arraySize]); void showgrid( int ar[arraySize][arraySize]); int main () { srand( time( NULL ) ); initarrays( grid); cout << "Starting grid: " << endl; showgrid(grid); cout << endl << endl; scramble( grid); cout << "Scrambled grid: " << endl; showgrid( grid); } void initarrays( int ar[arraySize][arraySize]) { int num = 1; int row, col; for (row = 0; row < arraySize; row++) { for (col = 0; col < arraySize; col++) { ar[row][col] = num; num++; } } } void scramble( int ar[arraySize][arraySize]) { int tmp, swprw, swpcl, row, col; for (row = 0; row < arraySize; row++) { for (col = 0; col < arraySize; col++) { swprw = rand() % arraySize; swpcl = rand() % arraySize; tmp = ar[swprw][swpcl]; ar[swprw][swpcl] = ar[row][col]; ar[row][col] = tmp; } } } void showgrid( int ar[arraySize][arraySize]) { int row, col; for (row = 0; row < arraySize; row++) { for (col = 0; col < arraySize; col++) { cout << ar[row][col] << " \t"; } cout << endl; } } Note that by using functions for discrete actions the code takes on a structure that is easy to follow. This will be important as your projects get larger.
#4 Guest_rlhh*
Re: Generating a random number without repetition
Posted 23 April 2010 - 11:22 PM
Actually I'm trying to create a 9x9 array where the first 3x3, the first row and the first column are filled with numbers.
xxxxxxxxx
xxx000000
xxx000000
x00000000
x00000000
x00000000
x00000000
x00000000
x00000000
As stated previously, the numbers cannot repeat for the first row & column and the numbers couldn't be repeated for the first 3x3 grid.
After that, I'll allow the user to input a number into any of the 0(s) to check see if the number is a repetition and that is why I want to test it out one by one instead of shuffling it.
Was This Post Helpful? 0
#5 IngeniousHax
-
- |>|20-514<|{3|2
Reputation: 84
- Posts: 1,385
- Joined: 28-March 09
Re: Generating a random number without repetition
Posted 23 April 2010 - 11:46 PM
maybe something like:
num = (rand()%9 + rand()%9) / 2 // Just a thought
#6 CTphpnwb
Reputation: 3872
- Posts: 14,201
- Joined: 08-August 08
Re: Generating a random number without repetition
Posted 24 April 2010 - 05:32 AM
rlhh, on 24 April 2010 - 01:22 AM, said:
Actually I'm trying to create a 9x9 array where the first 3x3, the first row and the first column are filled with numbers.
Well then it's just a matter of populating the first row and column with random unique numbers and shuffling only them. That should be easy for you to do, given the code I've posted.
This post has been edited by CTphpnwb: 24 April 2010 - 05:33 AM
#7 Guest_rlhh*
Re: Generating a random number without repetition
Posted 24 April 2010 - 06:01 AM
Yeah, I've got the grid to be printed the way I want thanks to your code.
Now my next challenge is checking whether a number the user entered is already in the row, box or column.
As far as I'm concerned, I'll get the user to input the x and y axis and the number.
First I'll run a for loop to check the x-axis, then the y-axis, then the box.
What do I do after checking? How do I continue the program until every field is filled with the correct number?
#include <stdio.h> #include <stdlib.h> #include <time.h> const int arraySize = 9; void initarrays( int ar[arraySize][arraySize]); void scramble( int ar[arraySize][arraySize]); void initarrays_row( int ar[arraySize][arraySize]); void scramble_row( int ar[arraySize][arraySize]); void initarrays_column( int ar[arraySize][arraySize]); void scramble_col( int ar[arraySize][arraySize]); void showgrid( int ar[arraySize][arraySize]); void user_input( int ar[arraySize][arraySize]); int main () { srand( time( NULL ) ); int grid[9][9]={}; initarrays( grid); printf("Starting grid:\n"); showgrid(grid); scramble( grid); initarrays_row( grid); scramble_row( grid); initarrays_column( grid); printf("\nScrambled grid:\n"); showgrid( grid); } void initarrays( int ar[arraySize][arraySize]) { int num = 1; int row, col; for (row = 0; row < 3; row++) { for (col = 0; col < 3; col++) { ar[row][col] = num; num++; } } } void scramble( int ar[arraySize][arraySize]) { int tmp, swprw, swpcl, row, col; for (row = 0; row < 3; row++) { for (col = 0; col < 3; col++) { swprw = rand() % 3; swpcl = rand() % 3; tmp = ar[swprw][swpcl]; ar[swprw][swpcl] = ar[row][col]; ar[row][col] = tmp; } } } void initarrays_row( int ar[arraySize][arraySize]) { int row, col, newcol=3; int temp; for (row = 1; row < 3; row++) { for (col = 0; col < 3; col++){ temp = ar[row][col]; ar[0][newcol] = temp; newcol++; } } } void scramble_row( int ar[arraySize][arraySize]) { int tmp,swpcl,col; for (col = 3; col < 9; col++) { swpcl = rand() % 9; if(swpcl!=0 && swpcl!=1 && swpcl!=2) { tmp = ar[0][swpcl]; ar[0][swpcl] = ar[0][col]; ar[0][col] = tmp; } } } void initarrays_column( int ar[arraySize][arraySize]) { int row, col, newrow=3; int temp; for (row = 0; row < 3; row++) { for (col = 1; col < 3; col++){ temp = ar[row][col]; ar[newrow][0] = temp; newrow++; } } } void scramble_col( int ar[arraySize][arraySize]) { int tmp, swprw, row; for (row = 3; row < 9; row++) { swprw = rand() % 9; if(swprw!=0 && swprw!=1 && swprw!=2) { tmp = ar[swprw][0]; ar[swprw][0] = ar[row][0]; ar[row][0] = tmp; } } } void showgrid( int ar[arraySize][arraySize]) { int row, col; for (row = 0; row < 9; row++) { for (col = 0; col < 9; col++) { printf("%d",ar[row][col]); if(col==8) printf("\n"); if(col==2 || col==5) printf(" "); if(row==2 && col == 8 || row==5 && col == 8) printf("\n"); } } } Was This Post Helpful? 0
#8 Guest_rlhh*
Re: Generating a random number without repetition
Posted 24 April 2010 - 06:28 AM
Sorry to be posting again but how do I check the box?
This is what I have for the input part.
void user_input( int ar[arraySize][arraySize]) { int x, y, num,row,col; int count = -1; printf("Please enter the x axis :"); scanf("%d", &x); printf("\nPlease enter the y axis :"); scanf("%d", &y); printf("\nPlease enter the number :"); scanf("%d", &num); for(col=0; col<9; col++){ if(ar[x][col] == num) count++; } for(row=0; row<9; col++){ if(ar[row][y] == num) count++; } if(count<=0) ar[x][y]=num; else printf("Wrong number!"); ar[x][y]=-2; } Was This Post Helpful? 0
#9 CTphpnwb
Reputation: 3872
- Posts: 14,201
- Joined: 08-August 08
Re: Generating a random number without repetition
Posted 24 April 2010 - 06:35 AM
rlhh, on 24 April 2010 - 08:01 AM, said:
First I'll run a for loop to check the x-axis, then the y-axis, then the box.
What do I do after checking? How do I continue the program until every field is filled with the correct number?
I would do it by using a separate one dimensional array to hold the nine numbers. I'd scramble that array, then use the first 5 numbers of it to populate the first row and the first columns of the second two rows.
#10 NickDMax
Reputation: 2255
- Posts: 9,245
- Joined: 18-February 07
Re: Generating a random number without repetition
Posted 24 April 2010 - 10:36 PM
I found this problem interesting so I put my little brain to it and came up with this. It is more abstract that what you are looking for but it also does what you are looking to do.
By abstract I mean that my version will work with any (N^2)x(N^2) grid. So the 9x9 or 16x16, or 25x25 etc....
What I did was this: You choose a row and col that you would like to pick numbers for. The program will also fill out the square (block) where the row and column meet. So for example as it is the program has a grid of 16x16 (4 blocks by 4 blocks), and is set to row 8, col 8, which meet the 3rd block over 3 blocks down...
The first thing the program does is fill the target block with the numbers 1-N^2. Then it scrambles these numbers randomly.
Next is uses the numbers in the block to fill out the row and col -- keeping the same order as they are in the block. The result is the numbers 1-N^2 uniquely represented in the row, col, and block. As it is filling out the row/col it also create a mask for the row and col to tell which numbers are "free to be scrambled" -- those numbers that are part of the block are NOT free to be scrambled, but the numbers that are just part of the row or col and NOT part of the block ARE free to be scrambled.
So then using the mask I scramble those numbers in the row or col that were NOT part of the block. (this is done in the very last for-loop in the initRandom() function, if you comment out this section it is easier to see how the numbers are placed into the grid).
I doubt this program will be much help to you, but I hope that the technique might be helpful... To set it to the state that you need, set BASE_SIZE to 3, and call initRandom(grid, 0, 0).
#include <iostream> #include <algorithm> #include <iomanip> #include <cstdlib> // BASE_SIZE is the block size of the grid. For example if BASE_SIZE is 3, you get a 9x9 grid (3 blocks x 3 blocks). const int BASE_SIZE = 4; const int GRID_SIZE = BASE_SIZE * BASE_SIZE; const int CELL_SIZE = 2; //Number of digits/padding for cells -- 2 is good for BASE_SIZE < 9 since 9x9 = 81. //A typedef for our grid typedef int Grid[GRID_SIZE][GRID_SIZE]; void clearGrid(Grid& grid); void displayGrid(std::ostream& out, Grid& grid); void initRandom(Grid& grid, int x, int y); int main() { std::srand(std::time(0)); Grid grid; initRandom(grid, 8, 8); displayGrid(std::cout, grid); return 0; } void displayGrid(std::ostream& out, Grid& grid) { out << '\n'; //start on a new line char fillch = out.fill(); for(size_t y = 0; y < GRID_SIZE; ++y) { for(size_t x = 0; x < GRID_SIZE; ++x) { out << std::setw(CELL_SIZE) << grid[x][y] << ((x % BASE_SIZE == (BASE_SIZE - 1)) ? " |" : " "); } out << '\n'; if(y % BASE_SIZE == BASE_SIZE - 1) { out << std::setfill('-') << std::setw(GRID_SIZE*(CELL_SIZE+1) + BASE_SIZE) << ""; out << std::setfill(fillch)<< '\n'; } } out << std::endl; } void clearGrid(Grid& grid) { for(size_t y = 0; y < GRID_SIZE; ++y) { for(size_t x = 0; x < GRID_SIZE; ++x) { grid[x][y] = 0; //(x + y) % GRID_SIZE+1; } } } void initRandom(Grid& grid, int x, int y) { //start out with the grid in a known state... clearGrid(grid); //begins some calculations we will need. size_t xStartBase = (x / BASE_SIZE); //tells us which block x start in... size_t xStartBlock = (x / BASE_SIZE) * BASE_SIZE; // gives us the col for the first col of this block. size_t yStartBase = (y / BASE_SIZE); //tells us which block y start in... size_t yStartBlock = (y / BASE_SIZE) * BASE_SIZE; // gives us the row for the first row of this block. // fill the block with numbers... for(size_t i = 0; i < BASE_SIZE; ++i) { for(size_t j = 0; j < BASE_SIZE; ++j) { grid[xStartBlock + j][yStartBlock + i] = j*BASE_SIZE + i + 1; } } //then scramble those numbers.... for(size_t i = 0; i < BASE_SIZE; ++i) { for(size_t j = 0; j < BASE_SIZE; ++j) { std::swap( grid[xStartBlock + std::rand()%BASE_SIZE][yStartBlock + std::rand()%BASE_SIZE], grid[xStartBlock + std::rand()%BASE_SIZE][yStartBlock + std::rand()%BASE_SIZE] ); } } //row and col are Boolean masks, if row[n] is zero then grid[n][y] is in our target block and should not be scrambled. int row[GRID_SIZE]; int col[GRID_SIZE]; size_t index = 0; //Precalculate some base offsets to produce the correct cycles or columns/rows // this is a bit of mathemagic for picking the numbers correctly from the block and putting them into a row/col xStartBase = (y-xStartBase) % BASE_SIZE + yStartBlock; yStartBase = (x-yStartBase) % BASE_SIZE + xStartBlock; for(size_t i = 0; i < BASE_SIZE; ++i) { for (size_t j = 0; j < BASE_SIZE; ++j) { row[index] = !(index >= xStartBlock && index < xStartBlock + BASE_SIZE); col[index] = !(index >= yStartBlock && index < yStartBlock + BASE_SIZE); //std::cout << ((y-xStartBase) % BASE_SIZE + i ) % BASE_SIZE << " "; if (row[index]) { grid[index][y] = grid[xStartBlock + j][xStartBase + i]; } //else {grid[index][y] = 0; } if (col[index]) { grid[x][index] = grid[yStartBase + i][yStartBlock + j]; } //else {grid[x][index] = 0; } index++; } } // scramble those numbers that are not part of the block. for(size_t i = 0; i < 3*GRID_SIZE; ++i) { size_t r1 = std::rand() % GRID_SIZE; size_t r2 = std::rand() % GRID_SIZE; size_t r3 = std::rand() % GRID_SIZE; size_t r4 = std::rand() % GRID_SIZE; //since it is fairly likely that one or the other of our random values lies inside the block // I gave two chances, I could increase this, but is seems to be working fine. if(row[r1] && row[r2]) { std::swap(grid[r1][y], grid[r2][y]); } else if(row[r2] && row[r3]){ std::swap(grid[r2][y], grid[r3][y]); } //I choose 4 random values to ensure that the row and col were not scrambled in the same way. if(col[r3] && col[r4]) { std::swap(grid[x][r3], grid[x][r4]); } else if(col[r3] && col[r2]){ std::swap(grid[x][r3], grid[x][r2]); } } } I had fun. The "mathemagic" part actually gave me a bit of trouble at first. I had to walk away for a little while and then when I cam back it seems really simple (well it can't be too simple since I was unable to write up a good explanation of why it works and had to resort to "mathematic" as a description... it really is not hard, I just don't know how to describe it at this point).
#11 baavgai
Reputation: 7507
- Posts: 15,558
- Joined: 16-October 07
Re: Generating a random number without repetition
Posted 25 April 2010 - 04:05 AM
To the orgininal question. If you know the contents of the set you're pulling from, you create a list of all values and then just randomly select from the list.
Here's and example:
#include <stdio.h> #include <stdlib.h> #include <time.h> typedef struct { int num[9]; int size; } AvailNum; void initAvailNum(AvailNum *an) { int i; an->size=9; for(i=0; i<an->size; i++) { an->num[i] = i+1; } } int pickAvailNum(AvailNum *an) { if (an->size==0) { return -1; } else if (an->size==1) { an->size = 0; return an->num[0]; } else { int i = rand() % an->size--; int n = an->num[i]; if (i<an->size) { // we didn't pick the last one an->num[i] = an->num[an->size]; } return n; } } void test() { AvailNum an; int n; initAvailNum(&an); while ((n=pickAvailNum(&an))!=-1) { printf("%d ",n); } printf("\n"); } int main(void) { srand(time(NULL)); test(); test(); test(); return 0; } Now, rather than responding to your code in #7, I'm responding to your problem in #4. Which, honestly, is more entertaing.
Here, we randomly fill a row with values 1..9. Then a column, excluding the value already in that column. Then a 3x3 box, exculding the values already there. I'm hoping that code for exclusion might give you some ideas.
#include <stdio.h> #include <stdlib.h> #include <time.h> typedef struct { int num[9]; int size; } AvailNum; #define ROWS 9 #define COLS 9 typedef int Grid[ROWS][COLS]; void cleargrid(Grid); void initarrays_row(Grid); void initarrays_col(Grid); void initarrays_box(Grid); void showgrid(Grid); void initAvailNum(AvailNum *); int pickAvailNum(AvailNum *); void removeAvailNum(AvailNum *, int value); int main () { srand( time( NULL ) ); Grid grid; cleargrid(grid); printf("Starting grid:\n"); showgrid(grid); initarrays_row(grid); initarrays_col(grid); initarrays_box(grid); printf("\nScrambled grid:\n"); showgrid(grid); } void initAvailNum(AvailNum *an) { int i; an->size=9; for(i=0; i<an->size; i++) { an->num[i] = i+1; } } int pickAvailNum(AvailNum *an) { if (an->size==0) { return -1; } else if (an->size==1) { an->size = 0; return an->num[0]; } else { int i = rand() % an->size--; int n = an->num[i]; if (i<an->size) { // we didn't pick the last one an->num[i] = an->num[an->size]; } return n; } } void removeAvailNum(AvailNum *an, int value) { int i; for(i=0; i<an->size; i++) { if (an->num[i]==value) { // found it int j=i; an->size--; for(; j<an->size; j++) { an->num[j] = an->num[j+1]; } return; } } } void cleargrid(Grid grid) { int row, col; for (row=0; row<ROWS; row++) { for (col=0; col<COLS; col++) { grid[row][col] = 0; } } } void initarrays_row(Grid grid) { AvailNum an; int col; initAvailNum(&an); for (col=0; col<COLS; col++) { grid[0][col] = pickAvailNum(&an); } } void initarrays_col(Grid grid) { AvailNum an; int row; initAvailNum(&an); // remove the num in the row removeAvailNum(&an, grid[0][0]); for (row=1; row<ROWS; row++) { grid[row][0] = pickAvailNum(&an); } } // the most fun void initarrays_box(Grid grid) { AvailNum an; int col, row; initAvailNum(&an); // remove the nums in the row and col removeAvailNum(&an, grid[0][0]); removeAvailNum(&an, grid[0][1]); removeAvailNum(&an, grid[0][2]); removeAvailNum(&an, grid[1][0]); removeAvailNum(&an, grid[2][0]); for (row=1; row<3; row++) { for (col=1; col<3; col++) { grid[row][col] = pickAvailNum(&an); } } } void showgrid(Grid grid) { int row, col; for (row=0; row<ROWS; row++) { for (col=0; col<COLS; col++) { printf("%d", grid[row][col]); if(col==2 || col==5) { printf(" "); } } printf("\n"); if(row==2 || row==5) { printf("\n"); } } } This all looks suspiciously like a sudoku problem. For sudoku specifically, you need to check if a given value exists on a row, col, and box. You may actually find the AvailNum code I've provided useful for that, since you can check off what you've already found.
Hope this helps.
How to Generate Random Numbers in C++ Without Repetition
Source: https://www.dreamincode.net/forums/topic/169884-generating-a-random-number-without-repetition/