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

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 o开发者_运维问答n 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

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

Fastest way is somthing like this:

1. You have array of n imgs URL & grid x*y
2. Find a central cell of the grid.
3. Randomly extract imgs URL from array and put each URL around central cell (first URL put to the center)
4. Do it until you don't fill all grid cells or while you have URLs in array.
5. If every URL is used then you should take URLs from concentric circles that you are made. Folow from the central cell to the circle with the bigest radius.
6. URLs taken by this method you should randomly put around biggest circle.

This algorithm will work if you have enough URLs for drawing less then 2 disks to the grid.

You can successfully modify it if you will follow the rule that URLs from one set must fill as big circle as it can.

What you want is a space-filling-curve for example a hilbert curve. It fills your grid with a continous line separating each square by only 1 bit. Because the nature of a sfc is to recursivley fill the space and maintain a neighborhood you can exploit this and place the picture along the line. If you don't want to place the same picture in the direct neighboorhood you can use a depth-seach on the sfc on each node eliminates copies.