2

我需要随机生成一个 NxN 整数矩阵，范围在 1 到 K 之间，这样所有行和列都分别具有它们的元素成对不同的属性。

例如对于 N=2 和 K=3

还行吧：

1 2
2 1

这不是：

1 3
1 2

（请注意，如果 K < N 这是不可能的）

当 K 比 N 足够大时，一个足够有效的算法就是生成一个由 1..K 个整数组成的随机矩阵，检查每一行和每一列是否成对不同，如果不是再试一次。

但是如果 K 比 N 大不了多少呢？

4

3 回答 3

1

这不是一个完整的答案，而是一个关于不起作用的直观解决方案的警告。我假设“随机生成”是指在所有现有此类矩阵上具有统一概率。

对于 N=2 和 K=3，这里是可能的矩阵，直到集合 [1..K] 的排列：

1 2    1 2    1 2
2 1    2 3    3 1

（因为我们忽略了集合 [1..K] 的排列，我们可以假设 wlog 的第一行是1 2）。

现在，一种直观（但不正确）的策略是逐个绘制矩阵条目，确保每个条目与同一行或列上的其他条目不同。要了解它为什么不正确，请考虑我们已经绘制了这个：

1 2
x .

我们现在正在绘制 x。x 可以是 2 或 3，但如果我们给每个可能性 1/2 的概率，那么矩阵

1 2
3 1

最后会得到 1/2 的概率，而它应该只有 1/3 的概率。

于 2012-08-08T09:08:24.257 回答
0

这是一个（文本）解决方案。我不认为它提供了很好的随机性，但无论如何它对您的应用程序来说可能没问题。

让我们使用以下算法在 [0;K-1] 范围内生成一个矩阵（如果您愿意，您将对所有元素执行 +1）：

  • 使用您想要的任何随机方法生成第一行。
  • 每个数字将是随机序列的第一个元素，计算方式是保证您在后续行中没有重复，即对于任何不同的列 x 和 y，您将有 x[i]!=y[i ] 对于 [0;N-1] 中的所有 i。
  • 计算前一行的每一行。

所有算法都基于具有我提到的属性的随机生成器。通过快速搜索，我发现Inversive congruential generator满足此要求。这似乎很容易实现。如果 K 是素数，则有效；如果 K 不是素数，请参见同一页上的“复合逆生成器”。也许处理完美的平方或立方数会有点棘手（你的问题听起来像数独 :-)），但我认为通过创建具有 K 的素数和不同参数化的复合生成器是可能的。对于所有生成器，每列的第一个元素是种子。

无论 K 的值是多少，复杂度仅取决于 N，并且为 O(N^2)。

于 2012-08-08T11:47:44.040 回答
0
  1. 确定性地生成具有所需行和列属性的矩阵。如果 K > N，这可以通过以 i 开始第 i 行并用 i+1、i+2 等填充行的其余部分来轻松完成，在 K 之后回绕回 1。其他算法也是可能的。
  2. 随机排列列，然后随机排列行。

让我们展示置换行（即取出整行并以某种顺序从它们中组装一个新矩阵，每行可能处于不同的垂直位置）使行和列的所需属性保持不变，假设它们之前是正确的。同样的推理也适用于列排列，以及任何一种排列的任何序列。

  1. 简单地说，置换行不能改变在每一行中没有元素出现多次的属性。
  2. 在特定列上排列行的效果是重新排序该列中的元素。这适用于任何列，并且由于重新排序元素不能产生以前没有的重复元素，因此置换行不能改变在每列中没有元素出现多次的属性。

我不确定该算法是否能够生成所有可能的满足矩阵，或者如果可以，它是否会以相等的概率生成所有可能的满足矩阵。另一个我没有答案的有趣问题是：需要多少轮行排列然后列排列？更准确地说，是否有任何有限的 row-perm-then-column-perm 轮次序列等效于有限数量的（或特别是一个）row-perm-then-column-perm 轮次？如果是这样，那么在第一行和第一列排列之后的进一步排列不会获得任何东西。也许有较强数学背景的人可以发表评论。但无论如何它可能已经足够好了。

于 2012-08-09T07:05:40.073 回答