c-从10x10阵列开始，我如何选择10个随机站点

Question

我正在尝试编写C代码，从10x10的网格中随机选择10个站点。我考虑的方法是给每个单元格分配一个介于0和RAND_MAX之间的随机数，然后选出10个最小/最大的值。但我对如何真正编码这样的东西知之甚少：/

我以前使用过伪随机数生成器，所以我可以完成这一部分。

Answer 1

只需生成2个0到9之间的随机数，然后从数组中选择随机元素，如：

arr[rand1][rand2];

循环做10次。没有必要让它变得更复杂。

Answer 2

为了稍微简化，将10x10数组视为100个元素的等效线性数组。现在的问题变成了从一组100中挑选10个不同的数字。要获得第一个索引，只需在0到99之间随机选择一个数字。

int hits[10];  /* stow randomly selected indexes here */
hits[0] = random1(100);  /* random1(n) returns a random int in range 0..n-1 */

第二个数字几乎同样简单。从剩下的99种可能性中选择另一个数字。Random1返回一个连续范围0..99的数字；然后你必须将其映射到破碎的范围0.hits[0]-1，hits[0]+1..99。

hits[1] = random1(99);
if (hits[1] == hits[0]) hits[1]++;

现在，对于第二个数字，映射开始变得有趣，因为它需要一些额外的工作来确保新数字与现有的两个选择不同。

hits[2] = random1(98);
if (hits[2] == hits[0]) hits[2]++;
if (hits[2] == hits[1]) hits[2]++;
if (hits[2] == hits[0]) hits[2]++; /* re-check, in case hits[1] == hits[0]+1 */

如果在执行过程中对命中数组进行排序，就可以避免重新检查元素的唯一性。把所有东西放在一起：

int hits[10];
int i, n;
for (n = 0; n < 10; n++) {
    int choice = random1( 100 - n );  /* pick a remaining index at random */
    for (i = 0; i < n; i++) {
        if (choice < hits[i])  /* find where it belongs in sorted hits */
            break;
        choice++;  /* and make sure it is distinct *
                   /* need ++ to preserve uniform random distribution! */
    }
    insert1( hits, n, choice, i );
            /* insert1(...) inserts choice at i in growing array hits */
}

您可以使用hits从10x10阵列中提取元素，如下所示：

array[hits[0]/10][hits[0]%10]

Answer 3

for (int i = 0; i < 10; i++) {
    // ith random entry in the matrix
    arr[rand() % 10][rand() % 10];
}

Answer 4

根据Peter Raynham的回答修改了这一点-我认为其中的想法是正确的，但他的执行过于复杂，没有正确映射范围：

为了稍微简化，将10x10阵列视为100个元素的等效线性阵列。现在的问题变成了从一组100中挑选10个不同的数字。

要获得第一个索引，只需在0到99之间随机选择一个数字。

int hits[10];  /* stow randomly selected indexes here */
hits[0] = random1(100);  /* random1(n) returns a random int in range 0..n-1 */

第二个数字几乎同样简单。从剩下的99种可能性中选择另一个数字。Random1返回一个连续范围0..99的数字；然后你必须将其映射到破碎的范围0.hits[0]-1，hits[0]+1..99。

hits[1] = random1(99);
if (hits[1] >= hits[0]) hits[1]++;

请注意，您必须映射完整的命中范围[0]。。98命中[0]+1.99

对于另一个数字，您必须与以前的所有数字进行比较，因此对于第三个数字，必须进行

hits[2] = random1(98);
if (hits[2] >= hits[0]) hits[2]++;
if (hits[2] >= hits[1]) hits[2]++;

你不需要对数字进行排序！把所有东西放在一起：

int hits[10];
int i, n;
for (n = 0; n < 10; n++) {
    int choice = random1( 100 - n );  /* pick a remaining index at random */
    for (i = 0; i < n; i++)
        if (choice >= hits[i])
            choice++;
    hits[i] = choice;
}

您可以使用hits从10x10阵列中提取元素，如下所示：

array[hits[0]/10][hits[0]%10]

Answer 5

如果您希望从网格中选择的随机单元格是唯一的，那么您似乎真的想构建随机排列。在这种情况下：

• 将单元格编号0..99放入1D数组
• 采用一些洗牌算法并用它投掷数组
• 从打乱的数组中读取前10个元素

缺点：该算法的运行时间随着细胞数量的增加而线性增加。因此，出于实际原因，按照@PaulP.R.O.的说法做可能会更好。。。

Answer 6

hjhill的解决方案中存在一个微妙的错误。如果不对列表中的元素进行排序，则在扫描列表（内部for循环）时，需要在任何时候更改选择索引（choice++）时重新扫描。这是因为您可能会将其撞到列表中的前一个条目中，例如使用随机数：90、89、89。

完整代码：

int hits[10];
int i, j, n;
for (n = 0; n < 10; n++) {
    int choice = random1( 100 - n );  /* pick a remaining index at random */
    for (i = 0; i < n; i++) {
        if (choice >= hits[i]) {   /* find its place in partitioned range */
            choice++;
            for (j = 0; j < i; j++) {   /* adjusted the index, must ... */
                if (choice == hits[j]) {  /* ... ensure no collateral damage */
                    choice++;
                    j = 0;
                }
            }
        }
    }
    hits[n] = choice;
}

我知道有了五层嵌套，它变得有点难看了。当只选择几个元素（例如，100中的10个）时，它将具有比排序解决方案更好的性能；当选择许多元素（例如，100中的90个）时，性能可能比排序解决方案更差。