Picking random coordinates without duplicates?

Question

I want to choose random coordinates on a 8x8 board. The x and y coordinates can only be -8. -6, -4, -2, 0, 2, 4, 6, and 8. I want to choose random coordinates for 20 objects but I don't want any 2 objects to have the same coordinates. Program away in C++!

Answer 1

You've only got 9 possible values for each coordinate, so that's 81 possible points in all. The simplest solution would be to just enumerate all possible points (eg: in an array or vector), and then randomly select 20.

You can randomly select 20 by picking an index from 0 to 80, swapping that element of the array with index 80, and then randomly picking an index from 0 to 79, swapping that with index 79, and so on 20 times. Then the last 20 elements of your array will be 20 distinct random points.

Answer 2

Take all of the coordinate pairs in your set, and toss them into a list, and generate a random permutation of the list (standard algorithms exist for this, such as the algorithm Laurence is suggesting). Take the first 20 elements of the permutation.

Answer 3

If you can enumerate all coordinates on the board, you can use any sampling algorithm. You're on a 9x9 grid; just pick 20 values out of the range [0,80] and then translate them into grid coordinates:

// Say the number picked is "n"
int x = ((n % 9) - 4) * 2;
int y = ((n / 9) - 4) * 2;

You can use any sampling algorithm to generate the ns; check out the answers to this question, for example.

The advantage of this approach over generating the points explicitly is that you can save quite a bit of memory (and processing time) on large grids. If they're really large and you're picking a small simple, the obvious algorithm works fine too: Just pick a random point and try again if you already picked it. The only problem with this algorithm is that it can end up doing quite many retries if you're selecting a large fraction of a set.

Answer 4

Putting Laurence's algorithm in program. Its working fine.

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

//To store x and y coordinate of a point
struct Point
{
    int x, y;
};

int main()
{
    vector<Point> v;
    Point p;
    //Populate vector with 81 combinations.
    for(int i = -8; i < 10; i += 2)
    {
        for(int j = -8; j < 10; j += 2)
        {
            p.x = i;
            p.y = j;
            v.push_back(p);
        }
    }
    srand(time(NULL));

    int lastIndex = 80;
    for(int i = 0; i < 20; i++)
    {
        int randNum = rand() % (81-i);
        //Swap to isolate chosen points.
        std::swap(v[randNum], v[lastIndex-i]); 
    }

    //Print chosen random coordinates
    cout<<"Random points chosen are "<<endl;
    for(int i = 61; i < 81; i++)
    {
        Point p = v[i];
        cout<<p.x<<"\t"<<p.y<<endl;
    }
}

Answer 5

You could use std::random_shuffle for instance, since you have a finite number of integer coordinates. So just shuffle that set of vectors/positions around. You can also pass your own RNG to random_shuffle as a function object.

Example:

#include <algorithm> //for copy and random_shuffle
#include <utility>   //for pair and make_pair
#include <vector>

...

std::vector<std::pair<int, int> > coords;
std::vector<std::pair<int, int> > coords20(20);
for(int y=-8; y<=8; y+=2)
    for(int x=-8; x<=8; x+=2)
        coords.push_back(std::make_pair(x,y));

std::random_shuffle(coords.begin(), coords.end());    
std::copy(coords.begin(), coords.begin() + 20, coords20.begin());