I have a n x n grid filled with photo urls. How can I make sure photos do not appear together in c#

Question

I basically have a grid, lets say 100 x 100 which is filled with url's of a photo collection. Some of these are duplicates as I may only have 50 photos but I want to duplicate them to make sure the 100 x 100 grid is filled. I randomly fill the grid with the URL's and then display them which is fine. The problem I have is that obviously sometimes photos with the same URL are randomly places together either on the x axis or y axis or sometimes both.

How can I make sure that I fill the grid so that these images with the same URL are as far apart as possible thus preventing 2 of the same photos appearing next to each other.

Any help appreciated

Mike

Answer 1

If you really want "as far apart as possible" then (1) I bet you're out of luck and (2) if that were achievable it would probably produce not-very-random-looking results. But if all you want is "somewhat far apart", it's not so bad. Here are a few things you can do.

(1) Classify grid positions according to the parity of their x,y coordinates: that is, whether they're odd and even. Divide the photos into four roughly-equal-sized batches. Now select from different batches according to the parity of the coordinates. The following code (which is a bit too "clever"; sorry) does this, modulo bugs and typos.

System.Random rng = new System.Random();
for (int x=0; x<nx; ++x) {
  for (int y=0; y<ny; ++y) {
    k = ((x&1)<<1) + (y&1); // 0..3
    int n_photos_in_batch = (n_photos+3-k) >> 2;
    int photo_number = (rng.Next(0,n_photos_in_batch-1) << 2) + k;
    // use this photo
  }
}

Downsides: doesn't do anything to move copies of a photo any further away from one another than one step. Reduces randomness somewhat since all copies of any given photo will be in a fixed subset of positions; in some contexts this may be visible and look rather silly.

Variations: we're basically covering the grid with 2x2 tiles, and restricting the range of photos allowed to occur in each tile. You could use larger tiles, or differently-shaped tiles, or arrange them differently. For instance, if you say k = ((x&1)<<1) ^ (y&3) you get 2x2 tiles arranged in a kinda-hexagonal pattern, which is actually probably better than the version above.

(2) Loop over positions in your grid (raster order will do, though there might be better alternatives) and for each one choose a photo that (a) doesn't already occur too near to the position you're looking at and (b) is otherwise random. The following code (again, modulo bugs and typos) does something like this, though for large grids you might want to make it more efficient.

System.Random rng = new System.Random();
radius = MAX_RADIUS; // preferably not too big, so that the search isn't too slow
while ((2*radius+1)*(2*radius+1) >= n_photos) --radius; // gratuitously inefficient!
for (int x=0; x<nx; ++x) {
  for (int y=0; y<ny; ++y) {
    // which photos already appear too near to here?
    System.Collections.BitArray unseen = new System.Collections.BitArray(n_photos,True);
    for (x1=x-radius; x1<=x+radius; ++x1) {
      for (int y1=y-radius; y1<=y+radius; ++y1) {
        if (0 <= x1 && x1 < nx && 0 <= y1 && y1 < nx && (y1<y || (y1==y && x1<x))) {
          unseen[photos[x1,y1]] = False;
        }
      }
    }
    // now choose a random one of them
    int n_unseen = 0;
    for (int i=0; i<n_photos; ++i) if (unseen[i]) ++n_unseen;
    System.Debug.Assert(n_unseen>0, "no photos available");
    int j = rng.Next(0,n_unseen-1);
    for (int i=0; i<n_photos; ++i) {
      if (unseen[i]) {
        if (j==0) { photos[x,y] = i; break; }
        --j;
      }
    }
  }
}

Notes: This is much more expensive than option 1. The validity check on x1,y1 is gratuitously inefficient here, of course. So is the choice of radius. The obvious more-efficient versions of these, however, may break down if you adopt some of the variations I'm about to list. This code, as it stands, won't do anything to keep photos apart if there are fewer than 9. The choice of radius is actually completely bogus, for the grid-traversal order I've used, because there are never more than 2r^2+2r "excluded" positions; again, that may change if you traverse the grid in a different order. Etc.

Variations: there's no real reason why the region you search over should be square. Circular might well be better, for instance. You could, with some extra work, construct a region that always has exactly as many points in it as you have photos (though if you do that you'll get a mostly-periodic pattern of photos, so better to be a bit less aggressive ). It might be better to process the grid entries in a different position -- e.g., spiralling out from the centre.

(3) Option 2 above will keep photos unique within a certain range (about as large as it can be given how many different photos you have) but not care about keeping copies further away apart from that. You could, instead, decide how bad it is having two identical photos at any given distance and then choose photos to minimize total badness. This will be even more expensive than option 2. I shan't bother giving sample code; you can probably work out how you might do it.

[EDITED to add ...]

(4) Here's a cute variation on the theme of (1). It will work best when the grid is square and its size is a power of 2, but you can adapt it to work more generally. It takes time only proportional to the size of your grid, however many photos you have. For each position (x,y): Throw away all but the bottom k bits of the coordinates, for some k. Bit-reverse them and interleave the bits, giving a number m from 0 to 2^(2k)-1. Choose k so that this is somewhere on the order of, say, n_photos/4. Now, at position (x,y) you'll put photo number round(n_photos*m/2^(2k) + smallish_random_number). There are a few details I'll leave for you to fill in :-).