Choosing random coordinates without duplicates?

Question

I want to select random coordinates on an 8x8 board. The x and y coordinates can only be -8. -6, -4, -2, 0, 2, 4, 6, and 8. I want to select random coordinates for 20 objects, but I do not want any 2 objects to have the same coordinates. Programs off in C ++!

Answer 1

You have only 9 possible values ​​for each coordinate, so there are 81 possible points. The simplest solution would be to simply list all possible points (for example: in an array or vector), and then randomly select 20.

You can arbitrarily select 20 by choosing an index from 0 to 80, replacing this array element with an index of 80, and then arbitrarily choosing an index from 0 to 79, replacing it with an index of 79, etc. 20 times. Then the last 20 elements of your array will consist of 20 different random points.

Answer 2

Take all the coordinate pairs in your set and move them to the list and create a random permutation of the list (there are standard algorithms for this, such as the algorithm proposed by Lawrence). Take the first 20 elements of the permutation.

Answer 3

If you can list all the coordinates on the board, you can use any selection algorithm. You are in a 9x9 grid; just select 20 values ​​from the range [0.80], and then translate them into the 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 n s; for example, see the answers to this question .

The advantage of this approach is that it generates points explicitly, because you can save quite a bit of memory (and processing time) on large grids. If they are really big and you choose a small simple one, the obvious algorithm works just as well: just select a random point and try again if you have already selected it. The only problem with this algorithm is that it can do quite a lot of repetition if you select most of the set.

Answer 4

Entering the Lawrence algorithm into the program. It works great.

 #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) { px = i; py = 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<<px<<"\t"<<py<<endl; } } 

Answer 5

For example, you can use std :: random_shuffle, since you have a finite number of integer coordinates. So just shuffle this 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());