Random generation problem

[plamkata]

Hi all.

Here is the problem I am trying to solve. I have one grid with dimension 10 by 10 (so it has 100 cells). I also have got few images and each image has number showing how many cells of the grid consist of that image. Let's say my images are image1 with number 32, image2 with number 12 and image3 with number 56. So it means that in 32 cells there are image1, in 12 cells - image2 and in 56 cells - image3.
I want to randomly scatter the images over the grid. The algorithm I am using is the following: I generate 32 random positions for image1, than 12 for image2 and the last 56 are for image3. I am using stdlib rand() function but the problem is that I don't get uniform randomization - the same images are very close to each other on the grid.
Maybe my algorithm is not very good and that is the problem.

Do you have any ideas how to fix that?

Thanks
Plamen Terziev

[jsmith]

Be sure that you only call srand() once in your program, and not inside a loop.

[writetonsharma]

i dont think this will solve the problem. rand() can generate any number, it never generate uniform numbers otherwise why it will be called rand().
so it is possible that all the image1 will be together
or it is possible that image1 will spread uniformly and all image2 will be very close.

you need to device your own uniform distribution function.

[jsmith]

@writeonsharma:

It is very common for programmers unfamiliar with srand()/rand() to do something like this:

for( int i = 0; i < 10; ++i ) {
   srand( time( 0 ) );
   cout << rand() << endl;
}

and then to wonder why it generates the same number 10 times most of the time.

The symptom being reported by OP is very indicative of the above. OP does not need to write his/her own RNG.

[tition]

With the numbers you gave, 56, 32, 12, it is clear that the 56 images of first type will be close to one another. So, can you explain in more detail the symptoms of the problem?

btw, you from Bulgaria? Cause your name looks Bulgarian to me

[seymore15074]

The problem being described needs elaborated on; I can't make heads or tails of it.

[plamkata]

Hi,

I am not using srand() in a loop. The problems is that I want the images to be randomly scattered but also I want them to be uniformed. So it is not exactly very random. The problem is more visible if I have 2 images - image1 with 90 and image2 with 10. In most of the cases the 10 images from the second type are close to each other and are not uniformly scattered. I suppose I need some my own uniform distribution function. Does anyone have an idea how that custom uniform function should look like?

Thanks,
Plamen Terziev

[jsmith]

rand() % N generates a perfectly uniform distribution in the range [0...N) where N divides 0x100000000. For any other value of N, the distribution is slightly biased toward the lower numbers. To correct for that, discard any random number generated by rand() that equals or exceeds 0xFFFFFFFF / N * N (using integer math).

[writetonsharma]

@jsmith

you are rigth jsmith...
Im not sayin that he need to generate his own rand() function.
but rand() % N for a range of 0-N will not always generate uniformly.. it may generate number very close or there may be alot of variation.

lets say we have 10 boxes.. 1-10
now doing rand() % 10 for 10 times not necessarily will generate a uniform distribution. it may alway generate 5 for each iteration.

In the above i mean to say use rand() function but add some logic so that the numbers are distributed uniformly.

:)

[jsmith]

Yes, of course. My statement is true if you consider the entire period of the RNG. If looking only at a small subset, as OP is, you are absolutely right.

Though I am a little confused about the initial request because it sounds like OP both wants randomness and non-randomness at the same time.

[writetonsharma]

hmmm...

i was thinking about some solution to the problem but a little busy with office work since a couple of days.. will think of a solution tonite.. :)

[jdd]

Since true randomization in such a small sample will not guarantee an even distribution, OP needs to fake it. OP can divide the 10x10 grid into several smaller grids, say 10 of them. Then, distribute 1/10^th of the images randomly throughout each smaller grid. Place 1/10^th of the images at [rand() % 10][0], place 1/10^th more at [rand() % 10][1], and so forth until the grid is full. Any given section of the grid should appear to have somewhat even proportions of the different images.

[writetonsharma]

jdd's idea looks cool..
good!!

[plamkata]

@jdd: Your idea really looks cool. I will try it and I think it will do the trick. Will let you know the result.

Thanks

[SouravDutta]

Well, we can increase the level of randomization to remove the clustering of the same images. Say, I generate 3 random numbers I, J and K. I and J will denote the positions within the grid so they will be in range [1..10] in this case. As there are 3 pictures to select from, K will be between [1..3]. After these numbers are generated, we place one copy of the Kth image at position (I,J) in the grid. This may give a better distribution.

But we do need to update the number of images left so that imageK is not selected when 0 copies of it are left to distribute. Further, the same I and J positions should not be reset .. in that case they will have to be generated again.
Dunno may be this is becoming a little tedious. :)

[jdd]

@SouravDutta
That is an interesting idea. If I understand correctly, though, it basically amounts to placing a random image (k) at a random location ( [i][j] ). Your method increases randomization and is certainly more proper in a statistical sense (I fully acknowledge that my method would make any statistician cringe). However, given that we are working with such a small sample, it would be no better than the original method at preventing grouping.