找到方链排列的算法

Question

如果连续数的总和始终是完美的平方,则排列是方形链.例如,

8 1 15 10 6 3 13 12 4 5 11 14 2 7 9 16

是数字1到16的平方链排列.我想编写一个程序来找到数字1到n的方形链式排列,n从1到100.

最简单的做法是按字典顺序排列n的所有排列(我知道如何写这个)并检查方形链条件,但这需要很长时间才能达到n大.

一个稍微好一点的方法是一次一个地选择我的排列中的数字,检查以确保我刚刚选择的数字在添加到前一个数字时形成一个正方形,并希望我将其设置到最后.不过,我不得不备份很多,而且我觉得它不会很有效率.

有没有更好的办法？另外,这是一个众所周知的问题吗？谢谢你的帮助.

Answer 1

有趣的问题; 我会开枪.将问题重新定位为TSP.

制作一个图形,其中节点是从1到100的整数(n您考虑的最大值).现在连接i,j如果i+j是一个完美的广场.这个问题问,"有哈密尔顿路径通过节点1最多n？"

制作一次图表,也许你可以调整路径i一旦你有它包括i+1.

这是最多14的图表:

                   13 --(25)-- 12 --(16)-- 4 --(9)-- 5 --(16)-- 11
                    |                                           |
                  (16)                                         (25)
                    |                                           |
8 --(9)-- 1 --(4)-- 3 --(9)-- 6 --(16)-- 10                     14
                                                                |
                                                               (16)
                                                                |
                                           9 --(16)-- 7 --(9)-- 2

直到添加14才连接图表,并且即使在添加14之后也没有哈密顿路径.这里有一个可爱的方式来绘制图表,其中添加了15个图表,可以轻松地显示如何在保持哈密尔顿路径的情况下使用16和17然后:

    12  11  10  09  08
13
                    07
14
                    06
15
                    05
    01  02  03  04

在方格纸上绘制并连接对角线和反对角线(例如12-13,14-11,...和09-07,10-06,...),它们是添加对的方式9或16.这里,我忽略了1和3之间的边缘,因为它没有帮助.想象一下,沿着对角线从8到1射击一个球,当它击中一个数字时,它会以直角反弹.球传到你给出的哈密尔顿路径(16分掉线).

要获得16的路径,只需将其添加到左下角.要获得17,将其固定在球进入8的路径上.

有合理的算法可以找到哈密顿路径,这种方法很可能比n根据你建议的方法检查每种方法更快.

我发现n <= 25解决方案只存在于15,16,17,23,25.请看!该序列在OEIS中.根据该页面,推测所有人都存在解决方案n > 24,所以显然这个问题是已知的,尽管我不一定称之为众所周知.