我正在尝试编写代码来检测矩阵是否为Hankel矩阵的排列，但我除了非常慢的暴力方法外想不到更有效的解决办法。这是规范。
输入：一个n乘n的矩阵M，其条目为1或0。
输入格式：以空格分隔的行。每行一行。例如
0 1 1 1
0 1 0 1
0 1 0 0
1 0 1 1
输出：将矩阵M的行和列进行排列组合，使得M成为一个汉克尔矩阵（如果可能）。汉克尔矩阵具有常数斜对角线（指正斜率的对角线）。
所谓的“排列组合”，是指我们可以对行和列采用不同的置换方式。
非常感谢您提供的任何想法。
检测汉克尔矩阵置换的算法
26
- Simd
12
10这可能会有用：https://dev59.com/AGIj5IYBdhLWcg3wCg_X - Peter de Rivaz
2这个问题的来源是什么？你指定输入格式让它看起来像是从一个竞赛编程比赛或者作业中提取出来的。如果是这样，那么你有额外的信息没有包含在内，应该自己解决。 - Douglas Zare
@PeterdeRivaz 谢谢。这似乎将复杂度降至类似于O(n^2 n!)的程度。我想知道这个问题是否是NP完全的？ - Simd
这似乎是很有可能的，这篇论文展示了一些涉及矩阵行列置换的相关问题是NP完全的。 - Peter de Rivaz
这也与已删除的MathOverflow帖子有关，该帖子询问给定大小的这种矩阵的数量http://mathoverflow.net/questions/202045吗？ - b_jonas
显示剩余7条评论
3个回答
2
不失一般性，我们假设0的数量比1的数量少。然后我们可以在Hankel矩阵中找到可能为0的对角线，以给出整个矩阵中所需的0的适当数量。这将给我们可能的Hankel矩阵。从那里，您可以计算每列中0的数量，并将其与原始矩阵列中的0的数量进行比较。完成此操作后，您就有了一个更小的空间来执行蛮力搜索：排列具有正确数量的0的列和行。
例如：OP建议使用7个0的4x4矩阵。我们需要使用集合{4,3,3,2,2,1,1}来分区。因此，或者分区是：
-{4,3}
-{4,2,1}（这种矩阵有两个）
-{3,3,1}
-{3,2,2}
-{3,2,1,1}（这种矩阵有两个）
这给我们带来了Hankel矩阵（不包括对称）。
例如：OP建议使用7个0的4x4矩阵。我们需要使用集合{4,3,3,2,2,1,1}来分区。因此，或者分区是：
-{4,3}
-{4,2,1}（这种矩阵有两个）
-{3,3,1}
-{3,2,2}
-{3,2,1,1}（这种矩阵有两个）
这给我们带来了Hankel矩阵（不包括对称）。
1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1
1 0 0 1 1 1 0 1 1 1 0 1 1 0 1 0
0 0 1 1 1 0 1 0 1 0 1 0 0 1 0 1
0 1 1 1 0 1 0 0 0 1 0 1 1 0 1 0
1 0 0 1 0 1 1 1 0 1 0 1
0 0 1 1 1 1 1 0 1 0 1 1
0 1 1 0 1 1 0 0 0 1 1 0
1 1 0 1 1 0 0 0 1 1 0 0
原矩阵的四列分别有3、1、2和1个0。将其与7种可能的汉克尔矩阵进行比较，得到2种可能性。
1 1 1 0 0 1 1 1
1 1 0 1 1 1 1 0
1 0 1 0 1 1 0 0
0 1 0 0 1 0 0 0
现在，只有4种可能的排列方式可以将原始矩阵映射到这些排列中的每一个：对于有2个和3个0的列，我们只有1种选择，但对于有1个0的列和行，我们有2种选择。检查这些排列，我们可以发现以下的Hankel矩阵是原始矩阵的一个排列。
0 1 1 1
1 1 1 0
1 1 0 0
1 0 0 0
- Degustaf
2
这个问题的第一个答案正确的是，行和列的置换不会改变行总和或列总和。
另一个容易观察到的事实是，在汉克尔矩阵中，两行之间的行总和之差为-1、0或1，并且每种情况都给我们的行带来了约束。如果差值为0，则进入变量等于退出变量；否则，我们知道哪个值为0，哪个值为1。
另一个容易观察到的事实是，在汉克尔矩阵中，两行之间的行总和之差为-1、0或1，并且每种情况都给我们的行带来了约束。如果差值为0，则进入变量等于退出变量；否则，我们知道哪个值为0，哪个值为1。
0 1 1 1
0 1 0 1
0 1 0 0
1 0 1 1
该矩阵的行和为3、2、1、3。满足差异要求的顺序是1 2 3 3和3 3 2 1，我们可以忽略反转，因为反转行和列的排列只会将矩阵旋转180度。因此，我们只需要考虑四个排列后的矩阵（行和中3的两种可能顺序和列和中3的两种可能顺序）：
0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0
1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1
我们可以进一步分析，通过强制前几行的和为1和2，我们限制了和为3的列的顺序，因为
0 0 1 0
0 0 1 1
不是一个有效的汉克尔矩阵的前两行。这种推理是否容易实现取决于您的编程范式。
请注意，在最坏情况下，这种推理仍然不会留下多项式数量的案例需要用蛮力法穷举。
- Peter Taylor
-1
以下是一些想法。
1)
行和列的置换保持行和列的总和不变：
1 0 1 0 - 2
0 0 0 1 - 1 row sums
1 0 0 0 - 1
1 1 1 0 - 3
| | | |
3 1 2 1
column sums
无论你如何排列行，行总和仍将是{2, 1, 1, 3}的某个排列；列总和不会改变。反之亦然。Hankel矩阵及其排列始终具有与列总和相同的行总和集。这为您提供了一个快速测试来排除一组不可行的矩阵。
我认为Hankel矩阵总是可以以这样的方式排列，使它们的行和列总和按升序排列，并且结果仍然是Hankel矩阵：
0 1 1 0 - 2 0 0 0 1 - 1
1 1 0 0 - 2 0 0 1 1 - 2
1 0 1 1 - 3 --> 0 1 1 0 - 2
0 0 1 0 - 1 1 1 0 1 - 3
| | | | | | | |
2 2 3 1 1 2 2 3
因此，如果一个矩阵可以排列成一个 Hankel 矩阵，那么它也可以被排列成一个行和列和升序的 Hankel 矩阵。也就是说，我们可以通过仅测试行和列和按升序排列的排列来减少需要测试的排列数。
我进一步假设对于任何具有两个或多个行具有相同和的 Hankel 矩阵，每个列的置换都有一个匹配的行的置换，这也会产生一个 Hankel 矩阵。也就是说，如果一个 Hankel 矩阵存在于一个列的置换中，则它存在于每个列的置换中——因为我们可以简单地将相应的行应用相同的置换并获得对称结果。
总之，我们只需要测试行或列的排列，而不是行和列。
应用于原始示例：
1 0 1 0 - 2 0 0 0 1 0 1 0 0 - 1 0 0 0 1
0 0 0 1 - 1 1 0 0 0 0 0 0 1 - 1 0 1 0 0
1 0 0 0 - 1 --> 1 0 1 0 --> 0 0 1 1 - 2 --> 0 0 1 1 = Hankel!
1 1 1 0 - 3 1 1 1 0 1 0 1 1 - 3 1 0 1 1
| | | |
3 1 2 1 permute rows into| ditto | try swapping
ascending order | for columns | top 2 rows
4)
最后，我提出，每个Hankel矩阵，其中有多行和多列具有相同的总和，都可以被置换成另一个Hankel矩阵，使得这些行和列按二进制数递增的顺序读取 - 对于行从左到右，对于列从上到下。也就是说：
0 1 1 0 0 1 0 1 0 0 1 1
1 0 0 1 0 1 1 0 0 1 0 1 New
1 0 1 0 --> 1 0 0 1 --> 1 0 1 0 Hankel
0 1 0 1 1 0 1 0 1 1 0 0
Original rows columns
Hankel ascending ascending
如果这是真的（我仍未决定），那么我们只需要创建和测试任何给定输入矩阵的一个排列。该排列将按升序排列行和列，并在平等总数的情况下，按其二进制数解释对它们进行排序。如果此结果矩阵不是 Hankel 矩阵，则没有排列可以使其成为 Hankel 矩阵。
希望这能帮助您找到算法的方向！
附录：反例？
尝试@orlp的示例：
0 0 1 0 0 0 1 0 0 0 0 1
0 1 0 1 0 1 0 1 0 1 1 0
1 0 1 1 --> 0 1 1 1 --> 0 1 1 1
0 1 1 1 1 0 1 1 1 0 1 1
(A) (B) (C)
- A: 原始的汉克尔矩阵。行总和为1、2、3、3；第3行和第4行不是二进制顺序。
- B: 交换第3行和第4行。第3列和第4列不是二进制顺序。
- C: 交换第3列和第4列。结果是汉克尔矩阵，满足所有属性。
尝试@Degustaf的例子：
1 1 0 1 0 1 0 0 0 0 1 0
1 0 1 0 1 0 0 1 0 1 0 1
0 1 0 0 --> 1 0 1 0 --> 1 0 0 1
1 0 0 1 1 1 0 1 0 1 1 1
(A) (B) (C)
- A: 原始的Hankel矩阵。行和为3、2、1、2。
- B: 重新排列，使得行和为1、2、2、3，并且行和为2的行按升序二进制顺序排列（即1001、1010）。
- C: 重新排列列和为1、2、2、3，其中两个列和为2的列按顺序排列（0101、1001）。结果是Hankel矩阵，并满足所有属性。请注意，列上的置换与行上的置换相匹配：从旧列中获取新列顺序的操作是{3、4、2、1}，与从A到B的操作相同。
注：我建议仅在行或列和的平局情况下使用二进制顺序(#4)，而不是替换(#2)中的排序。
- Brian L
10
谢谢您。很多非常有趣的想法！如果第三点正确，那么是否可以立即使用https://dev59.com/AGIj5IYBdhLWcg3wCg_X来提供O(n^2)时间算法？ - Simd
2点2也是错误的。具有两个长度为3的对角线和一个长度为2的零对角线的4x4矩阵无法转换为建议的形式。 - Degustaf
3从你的例子中，我倾向于认为你认为任何等于其转置的矩阵都是 Hankel 矩阵。但这不是问题中给出的定义。 - Peter Taylor
3@BrianL，您编辑了您的帖子以包含我的反例，试图驳斥它。但是您的结果是错误的。这里是为什么您的解决方案不是Hankel矩阵的解释：http://i.imgur.com/UgvIPM1.png 。所有对角线必须是恒定的。 - orlp
显示剩余5条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接