挑選隨機座標而不重複？

Question

我想在8x8板上選擇隨機座標。 x和y座標只能是-8。 -6，-4，-2，0，2，4，6和8.我想爲20個對象選擇隨機座標，但我不希望任何2個對象具有相同的座標。用C++編程！

Answer 1

對於每個座標，您只有9個可能的值，因此共有81個可能點。最簡單的解決方案是枚舉所有可能的點（例如：在一個數組或向量中），然後隨機選擇20.

您可以通過從0到80中選擇一個索引來隨機選擇20，將該元素索引爲80的數組，然後隨機選取一個從0到79的索引，並將索引替換爲索引79，依此類推20次。然後，數組中最後20個元素將是20個不同的隨機點。

Answer 2

將Laurence的算法放在程序中。它的工作正常。

#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

採取一切座標對在您所設定的，並把它們折騰到一個列表中，並生成列表的隨機置換（標準算法，這個存在，如算法勞倫斯是在暗示）。採取排列的前20個元素。

Answer 4

如果您可以枚舉電路板上的所有座標，則可以使用任何採樣算法。你在9x9網格上;只挑選20個值OUT [0,80]和範圍的然後將它們轉化爲網格座標：

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

可以使用任何採樣算法來生成n S;例如，請查看this question的答案。

這種方法明顯生成點的優點是可以在大型網格上節省相當多的內存（和處理時間）。如果它們真的很大，並且選擇了一個簡單的方法，那麼顯而易見的算法也可以正常工作：只要選擇一個隨機點，如果您已經選擇了一個點，就再試一次。這個算法唯一的問題是，如果你選擇了一大部分集合，它最終可能會做很多次重試。

Answer 5

例如，您可以使用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());