Cueillir des coordonnées aléatoires sans doublons?

Question

Je veux choisir des coordonnées aléatoires sur une carte 8x8. Les coordonnées x et y ne peuvent être que -8. -6, -4, -2, 0, 2, 4, 6 et 8. Je veux choisir des coordonnées aléatoires pour 20 objets mais je ne veux pas que 2 objets aient les mêmes coordonnées. Programmez loin en C++!

Answer 1

Vous ne disposez que de 9 valeurs possibles pour chaque coordonnée, soit 81 points possibles au total. La solution la plus simple consisterait simplement à énumérer tous les points possibles (par exemple: dans un tableau ou un vecteur), puis sélectionner au hasard 20.

Vous pouvez sélectionner au hasard 20 en sélectionnant un index de 0 à 80, en échangeant cet élément du tableau avec l'index 80, puis en choisissant au hasard un index de 0 à 79, permutant cela avec l'index 79, et ainsi de suite 20 fois. Ensuite, les 20 derniers éléments de votre tableau seront 20 points aléatoires distincts.

Answer 2

Mettre l'algorithme de Laurence dans le programme. Cela fonctionne bien.

#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 3

Prenez toutes les paires de coordonnées dans votre jeu, et les jeter dans une liste, et générer une permutation aléatoire de la liste (des algorithmes standards existent pour cela, tel que l'algorithme Laurence suggère). Prenez les 20 premiers éléments de la permutation.

Answer 4

Si vous pouvez énumérer toutes les coordonnées sur la carte, vous pouvez utiliser n'importe quel algorithme d'échantillonnage. Vous êtes sur une grille de 9x9; il suffit de choisir 20 des valeurs de la plage [0,80], puis les traduire en coordonnées de grille:

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

Vous pouvez utiliser un algorithme d'échantillonnage pour générer les n s; Découvrez les réponses à this question, par exemple. L'avantage de cette approche par rapport à la génération explicite des points est que vous pouvez économiser un peu de mémoire (et de temps de traitement) sur les grandes grilles. S'ils sont vraiment grands et que vous choisissez un petit simple, l'algorithme évident fonctionne bien aussi: choisissez un point aléatoire et réessayez si vous l'avez déjà choisi. Le seul problème avec cet algorithme est qu'il peut finir par faire assez de tentatives si vous sélectionnez une grande partie d'un ensemble.

Answer 5

Vous pouvez utiliser std :: random_shuffle par exemple, puisque vous avez un nombre fini de coordonnées entières. Il suffit donc de mélanger cet ensemble de vecteurs/positions autour. Vous pouvez également passer votre propre RNG à random_shuffle en tant qu'objet de fonction.

Exemple:

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