如何生成两个随机数X和Y，并确保它们不会重复？

Question

好的，我正在为WinForms编写扫雷应用程序。这是我的第一个C#应用程序，因此学习过程非常重要。我想随机生成两个数字并将它们放入两个单独的数组mineX和mineY中。这两个数组是地图上所有地雷放置位置的坐标。

问题在于，我希望确保当它随机生成这些数字时，X和Y永远不会相同。我已经进行了研究并知道如何生成单个数字并使每个数字唯一。我的问题是我希望两个随机数的组合是唯一的。

这是我的placeMines方法的代码。

    private void placeMines()
    {
        Random rnd = new Random();

        for (int i = 0; i < MINE_COUNT; i++)
        {               
                bombX[i] = rnd.Next(0, BOARD_X);
                bombY[i] = rnd.Next(0, BOARD_Y)'
        }
    }

这个问题似乎很简单，但是我怎么也想不出解决方法。

- Jonathan Carroll

---

您是指X和Y的组合必须是唯一的，还是一旦选择了X=2，就不能再选择其他X为2？ - Lasse V. Karlsen

对，两者的组合。X 可能实际上等于两个倍数，但相应的 Y 必须不同。 - Jonathan Carroll

如果不能重复，那么你就不需要随机数。所以不要使用随机数生成器！ - Cody Gray

重要的是要在解决这类问题时识别出模式。你不想要一堆随机值，而是想要固定值的随机顺序。这被称为洗牌，因其与洗牌一副牌非常相似而得名。洗牌的标准算法称为费舍尔-耶茨算法，该算法由两位统计学家于1938年解决。当您查询“c# random shuffle”或“c# fisher yates”时，您将获得大量的谷歌搜索结果。仅对于此网站，就有1.1万个搜索结果，我们尽量不再添加更多 :) - Hans Passant

Answer 1

1. 创建可能的地雷位置列表。
2. 从列表中随机选择一个项目并将其删除。
3. 重复步骤2，直到有足够的地雷。

示例代码：

const int BOARD_X = 10;
const int BOARD_Y = 6;
const int MINE_COUNT = 30;

List<int> positions = Enumerable.Range(0, BOARD_X * BOARD_Y).ToList();
var rnd = new Random();
for (int i = 0; i < MINE_COUNT; i++) {
    int index = rnd.Next(positions.Count);
    int pos = positions[index];
    positions.RemoveAt(index);
    int x = pos % BOARD_X, y = pos / BOARD_X;
    Console.WriteLine("({0}, {1})", x, y);
}

注意：如果位置数量很大，您可以使用位向量为空间优化算法。我会将这留作练习。

- Athari

---

谢谢！这很有意义。我还没有学习过列表，因此我认为没有办法比较一对整数作为一个整体，除非将它们转换为字符串（intX+","+intY），然后再比较字符串。感谢您的帮忙。 - Jonathan Carroll

@user3922214 如果您不想像这样将两个整数编码为一个整数（例如出于可读性的考虑），您可以使用元组（请参见另一个答案）、自定义类型或从.NET框架中找到适当的类型（例如WinForms、WPF、XNA中的点类）。 - Athari

Answer 2

生成一个包含两个整数字段x和y的结构体数组，并将该数组打乱。

Random _rand = new Random();
Position[] allPositions = GenerateAllPositions();

for (int i=allPositions.Length-1; i>=1; i--)
{
     int j = _rand.Next(0, i+1);
     // now swap
     Position tempPosition = allPositions[i];
     allPositions[i] = allPositions[j];
     allPositions[j] = tempPosition;
}

现在您可以拥有一个临时整型变量lastQueriedPositionIndex = 0，当您选择任何位置时，将其增加1。如果lastQueriedPositionIndex == allPositions.Length，则使lastQueriedPositionIndex=0并再次调用此“交换”例程。这是最坏情况下的O(n)解决方案，而不是Athari提出的O(n^2)解决方案——但是在小的棋盘尺寸中，您不会看到任何区别。

- fex

---

你为每个位置调用随机数生成器。我怀疑这可能会很慢，因为乘法器被O符号隐藏了。我认为没有明显的赢家。 - Athari

@Athari 随机数生成非常快，像这样洗牌列表（这是一种Fisher-Yates shuffle）几乎不需要任何资源。实际上，您的解决方案很慢，因为每次删除一个元素时，都需要复制每个项目。因此，这将是O(2N)读取，而您删除项目的解决方案将是O(N^2)读取。 - Scott Chamberlain

@ScottChamberlain 测量。当地雷比例合理时（在普通难度下经典扫雷游戏中为15％），此方法大约快5-10倍。当比例非常低时，我的方法可能更快，但几乎无法玩。 - Athari

@ScottChamberlain 有一个小问题要指出 - O(2N) 等同于 O(N)。 - pjs