Выбор случайных координат без дубликатов?

Question

Я хочу выбрать случайные координаты на доске 8х8. Координаты x и y могут быть только -8. -6, -4, -2, 0, 2, 4, 6 и 8. Я хочу выбрать случайные координаты для 20 объектов, но я не хочу, чтобы любые 2 объекта имели одинаковые координаты. Программа на C ++!

Answer 1

У вас есть только 9 возможных значений для каждой координаты, так что всего 81 возможных точек.Простейшим решением было бы просто перечислить все возможные точки (например, в массиве или векторе), а затем случайным образом выбрать 20.

Вы можете выбрать случайным образом 20, выбрав индекс от 0 до 80, поменяв местами этот элементмассива с индексом 80, а затем случайным образом выбирает индекс от 0 до 79, заменяет его индексом 79 и т. д. 20 раз.Тогда последние 20 элементов вашего массива будут составлять 20 различных случайных точек.

Answer 2

Если вы можете перечислить все координаты на доске, вы можете использовать любой алгоритм выборки. Вы на сетке 9x9; просто выберите 20 значений из диапазона [0,80] и затем переведите их в координаты сетки:

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

Вы можете использовать любой алгоритм выборки для генерации n с; проверить ответы на этот вопрос , например.

Преимущество этого подхода перед явным созданием точек состоит в том, что вы можете сэкономить немало памяти (и времени обработки) на больших сетках. Если они действительно большие, а вы выбираете маленькое простое, очевидный алгоритм тоже работает хорошо: просто выберите случайную точку и попробуйте снова, если вы уже выбрали ее. Единственная проблема с этим алгоритмом состоит в том, что он может выполнить довольно много попыток, если вы выбираете большую часть набора.

Answer 3

Возьмите все пары координат в вашем наборе, добавьте их в список и сгенерируйте случайную перестановку списка (для этого существуют стандартные алгоритмы, такие как алгоритм Лоренса). Возьмите первые 20 элементов перестановки.

Answer 4

Например, вы можете использовать std :: random_shuffle, поскольку у вас есть конечное число целочисленных координат. Так что просто перемешайте этот набор векторов / позиций вокруг. Вы также можете передать свой собственный RNG в random_shuffle как функциональный объект.

Пример:

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

Answer 5

Ввод алгоритма Лоуренса в программу. Работает нормально.

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