洗牌矩阵

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

Is there a simple way to fill and then shuffle the 2D array without creating a 1D array

当然可以。假设你已经填充了数组，要对其进行洗牌，为什么不随机生成 i1 ,i2, j1, j2 其中 i 和 j 是限制行和列。现在交换这些索引的值。这样说 0.5 x no.of.rows x no.of.cols ，这只是一个非常粗略的数字。基本上可以随心所欲地随机化它。任何小于 10^8 的都可以。

如果您担心生成重复对（对于较大的矩阵这应该不是真正的问题），您可以维护一个 std::set<pair<int, int> > 来存储生成的索引。每当您生成 i 和 j 时，请检查 {i, j} 是否存在。如果是，请重新生成它。

Answer 2

您可以在整数（您的一维）索引和 (i,j) 对之间选择双射函数，因此这将是将您的矩阵视为一维数组的方式。这叫做 'numbering scheme'.

类似于：

oneDindex(rowIndex,colIndex)=colIndex*rowCount+rowIndex;

逆变换

rowIndex=oneDIndex % rowCount

colIndex=oneDIndex / rowCount;

所以，你在[0, rowCount*colCount)中随机选择两个你想要交换的一维索引，通过逆变换得到它们的（rowIndex，colIndex）并交换它们。重复直到满意。

Answer 3

假设您的二维数组的维度为 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，都会在对每个索引进行操作之前将其转换为行 + 列。

洗牌矩阵

Shuffling a matrix

c++

arrays

multidimensional-array

stl

shuffle