一种检测Hankel矩阵排列的算法

Question

我正在尝试编写代码来检测矩阵是否是Hankel矩阵的排列,但除了非常慢的暴力之外我无法想到有效的解决方案.这是规格.

输入: n×n矩阵M,其条目为1或0.

输入格式:空格分隔的行.每行一行.例如

0 1 1 1
0 1 0 1
0 1 0 0
1 0 1 1

输出: M的行和列的排列,如果可能,则M是Hankel矩阵.Hankel矩阵具有恒定的倾斜对角线(正倾斜对角线).

当我说排列时,我的意思是我们可以将一个排列应用于行的顺序,并将一个可能不同的排列应用于列.

我会非常感谢任何想法.

Answer 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}；列总和将保持不变。反之亦然。汉克尔矩阵及其排列将始终具有与列和相同的行和集。这为您提供了一个快速测试来排除一组不可行的矩阵。

2）

我假设 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

因此，如果一个矩阵可以置换成汉克尔矩阵，那么它也可以置换成行列和升序的汉克尔矩阵。也就是说，我们可以通过仅测试行和列之和按升序排列的排列来减少需要测试的排列数量。

3）

我进一步假设，对于任何两行或更多行具有相同总和的汉克尔矩阵，每个列排列都有一个匹配的行排列，这也产生汉克尔矩阵。也就是说，如果汉克尔矩阵对于一种列排列存在，那么它对于每种列排列都存在——因为我们可以简单地将相同的排列应用于相应的行并获得对称的结果。

结果是我们只需要测试行或列的排列，而不是行和列。

应用于原始示例：

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）

最后，我假设，每个具有相同总和的多个行和列的汉克尔矩阵都可以排列成另一个汉克尔矩阵，其属性是，当读取为二进制数时，这些行和列按递增顺序排列- 从左到右读取行为右，列为从上到下。那是：

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)

• 答：原版汉克尔。行总和为 1, 2, 3, 3；第 3 行和第 4 行不是二进制顺序。
• B：交换第 3 行和第 4 行。第 3 列和第 4 列不是二进制顺序的。
• C：交换第 3 列和第 4 列。结果是 Hankel 并满足所有属性。

尝试@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)

• 答：原始汉克尔矩阵。行总和为 3, 2, 1, 2。
• B：重新排列，使行和为1、2、2、3，且和2的行按二进制升序排列（即1001、1010）
• C：将列总和重新排列为 1,2,2,3，其中总和 2 的两列按顺序排列 (0101, 1001)。结果是汉克尔并且满足所有性质。另请注意，列上的排列与行上的排列相匹配：旧列的新列顺序为 {3, 4, 2, 1}，与从 A 到 B 的操作相同。

注意：我建议二进制顺序 (#4) 仅适用于行或列总和的平局情况，而不是作为 (#2) 中排序的替代。