Member Avatar for iamboredguy

for my project, I need to generate an n*n matrix (n is user input) with numbers from 1 to x (x<n) positioned randomly. I tried implementing it with this code but it doesnt seem to work. x = n*n - number of holes.
the number of holes is user input with max value as n/2.
here's what I tried:

int a[10][10]={0};
                int n, holes, noofelements, randomno, rowpos, colpos; 
	int i,j;
	srand(time(NULL));
	do
	{
	 printf("Enter the size of the square (+ve integer, max 257): ");
	 scanf("%d", &n);
	 if (n<1 || n>256)
		 printf("Invalid size.");
	}
	while (n<1 || n>256);
	do
	{
	 printf("Enter the number of holes (max %d): ", n/2);
	 scanf("%d", &holes);
	}
	while (holes>(n/2));
	noofelements=n*n-holes;
	for (i=1; i<=noofelements; i++)
	{
		rowpos=rand()%n;
		colpos=rand()%n;
		a[rowpos][colpos]=i;
	}
	for (i=0; i<n; i++)
	{
		for (j=0; j<n; j++)
			printf("%d\t", a[i][j]);
		printf("\n");
	}

the generated matrix should have only 2 0's but it always has more than 2. any ideas?

  • 2 Contributors
  • 6 Replies
  • 226 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by iamboredguy

Dani AI

Generated

The symptom (more zeros than expected) comes from writing multiple times to the same random cell: random row/col picks collide, so you never place the full count of unique elements. 's sentinel-and-retry idea fixes correctness, but as the grid fills the retry loop does more and more work. A guaranteed, simple alternative is to list every cell once, shuffle that list, then use the first K positions — no retries, exactly K filled cells, and uniform placement.

The steps: (1) allocate a 1‑D array of indices 0..nn-1, (2) run an in-place Fisher–Yates shuffle, (3) map each chosen index to row/col with row = idx / n and col = idx % n, and (4) assign values to those cells (leave the rest as 0 or a sentinel). This uses O(nn) time and memory and avoids the collision problem entirely.

Example C sketch (replace input/limits checks with your own validation):

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int n, holes;
    if (scanf("%d %d", &n, &holes) != 2) return 1;
    int total = n * n;
    int fill = total - holes;
    int *grid = calloc(total, sizeof *grid);
    int *idx  = malloc(total * sizeof *idx);
    for (int i = 0; i < total; ++i) idx[i] = i;
    srand((unsigned)time(NULL));
    for (int i = total - 1; i > 0; --i) {
        int j = rand() % (i + 1);
        int tmp = idx[i]; idx[i] = idx[j]; idx[j] = tmp;
    }
    for (int i = 0; i < fill; ++i) grid[idx[i]] = i + 1;
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < n; ++c) printf("%d\t", grid[r * n + c]);
        printf("\n");
    }
    free(grid); free(idx);
    return 0;
}

Notes: use dynamic allocation for large n (avoid fixed 10x10), check for overflow when computing n*n, seed srand once, and if you need better randomness than rand() consider a modern PRNG. This approach guarantees the exact number of non-zero cells without repeated random attempts.

Recommended Answers

All 6 Replies

Member Avatar for Ancient Dragon

>> if (n<1 || n>256)

your array is only 10 rows and columns. If I enter a value of 255 then your program will crash bigtime. Instead of hard-coding a value like 256, create a define or const int to declare the array size and its limits

const int MaxSize = 10
int a[MaxSize][MaxSize];
...
...
if (n<1 || n>MaxSize)

now remember to decrement the value of n by one (range is 0 to (but not including) MaxSize) before using it as an index into the array.

Member Avatar for iamboredguy

I know about the size of the array. I just put 10 so that the program doesnt eat up too much memory during testing. I'm pretty sure I decremented the value of n as well. something else is wrong.

Member Avatar for Ancient Dragon

If you pre-fill all elements of the array with -1 then you will more easily see the cells that were never toched. And the reason is because the program generates random values for rowpos and colpos, and sometimes those values have already been generated. So instead of generating (5*5)-2 = 23 random values it generates something less than that.

One way to correct that would be to check the array to see of the values have been previously generated, and if they have generate new random values. If a[rowpos][colpos] has a values other than -1 then you need to generate new random values.

Probably a faster way to do it is to use two more int arrays, one for rowpos and the other for colpos, initialize each array with numbers from 0 to n, then randomly shuffle the rows. After than you don't need to generate any more random numbers, just use the arrays from row 0 to N the indices into array a[][],

Enter the size of the square (+ve integer, max 257): 5
Enter the number of holes (max 2): 2
-1      -1      8       19      11
16      -1      17      12      -1
-1      -1      -1      2       21
-1      -1      4       -1      20
10      18      22      15      23
Press any key to continue
Member Avatar for iamboredguy

nice idea. but how do I randomly shuffle a row? taking rowpos[]={0,1,2,3} how do I shuffle? using rand() won't work since I would have the same problem as before.

Member Avatar for Ancient Dragon

this should fix the problem

const int MaxN = 10;
...
...
	for(i = 0; i < MaxN; i++)
	{
		 for(j = 0; j < MaxN; j++)
			 a[i][j] = -1;
	}
...
...
... // code omotted
...
	for (i=1; i<=noofelements; i++)
	{
		do {
			rowpos=rand() % n;
			colpos=rand() % n;
		} while( a[rowpos][colpos] >= 0);
		a[rowpos][colpos]=i;
	}
Member Avatar for iamboredguy

that works. thanks a lot!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.