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

Question

我正在尝试编写代码来检测矩阵是否是 Hankel 矩阵的置换，但除了非常缓慢的蛮力之外我想不出有效的解决方案。这是规范。

输入:一个 n x n 矩阵 M，其元素为 1 或 0。

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

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

输出:M 的行和列的排列，使得 M 是 Hankel matrix如果可能的话。 Hankel 矩阵具有恒定的斜对角线(正斜率对角线)。

当我说排列时，我的意思是我们可以对行的顺序应用一种排列，对列的顺序应用可能不同的排列。

如果有任何想法，我将不胜感激。

Answer 1

不失一般性，我们假设 0 的数量少于 1 的数量。然后我们可以在汉克尔矩阵中找到可能为 0 的对角线，从而为我们提供整个矩阵中 0 的适当数量。并且，这将为我们提供可能的 Hankel 矩阵。从那里，您可以计算每列中 0 的数量，并将其与原始矩阵列中 0 的数量进行比较。完成此操作后，执行强力搜索的空间就会小得多:对具有正确数量的 0 的列和行进行置换。

示例: OP 建议使用带有 7 个 0 的 4x4 矩阵。我们需要使用集合 {4,3,3,2,2,1,1} 对其进行分区。所以，或者分区将是:

• {4,3}
• {4,2,1}(这些矩阵中的 2 个)
• {3,3,1}
• {3,2,2}
• {3,2,1,1}(这些矩阵中的 2 个)

这给了我们 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 种可能的 Hankel 矩阵进行比较，我们得到 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 个选择，还有 2 个带有 1 0 的行的选择。检查这些排列，我们看到以下 Hankel 矩阵是原始矩阵的排列

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