Picking random coordinates without duplicates?

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 开发者_如何学JAVAto have the same coordinates. Program away in C++!

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.

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.

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.

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;
    }
}

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());