c++ - 洗牌矩阵

Question

我需要用给定数量的特定值随机填充矩阵。 (出于某种原因，我有一个 C 二维数组)。我找到的简单解决方案是将二维数组解释为一维数组:(请忽略硬编码常量和临时随机对象):

int m[10][10] = {};

std::fill_n(&m[0][0], 24, -1);
std::shuffle(&m[0][0], &m[0][0] + 100, std::mt19937{std::random_device{}()});

但这似乎是有争议的，因为它是否是未定义的行为:

Is it legal to access a bidimensional array as if it where a one-dimensional one?

May I treat a 2D array as a contiguous 1D array?

要点是，即使保证底层数据是连续的而行之间没有填充，索引方案或递增 &m[0][0] int* 第一行之外的指针无效。

所以我正在寻找一种替代的安全方法。有没有一种简单的方法可以填充二维数组然后打乱顺序，而无需创建一维数组然后将其复制到矩阵中？

注意:矩阵的其余部分都是 0，因此不需要保留这些单元格。

Answer 1

假设您的二维数组的维度为 m X n，它已被初始化，并且您想进行就地随机洗牌。

很容易修改 Durstenfeld variant of the Fisher-Yates Shuffling algorithm为了这。以下是伪代码:

for i = m * n - 1 downto 1
    j = random integer in the range [0, i] (both inclusive)
    swap(a[i / n][i % n], a[j / n][j % n])

这本质上是原始算法，将数组视为 1d。但是，无论何时选择索引 i 和 j，都会在对每个索引进行操作之前将其转换为行 + 列。