寻找平方链排列的算法

Question

寻找平方链排列的算法

algorithmpermutation

14

排列称为平方链当且仅当连续的数之和始终为完全平方数。例如，

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，这将花费很长时间。

比较好的方法是逐个选择排列中的数字，并检查刚选择的数字加上前一个数字是否为完全平方数，希望能够完成整个排列。但是这样会经常回溯，效率可能不高。

有更好的方法吗？此问题是否为众所周知的问题？感谢您的帮助。

- A B

1

例如，1、2、3是否保证存在？ - parapura rajkumar

@MitchWheat 看起来我们有些混淆，他得到了两种类型的投票。 - Yuriy Faktorovich

1

为什么要关闭投票？原帖已经有两个解决方案了吗？ - parapura rajkumar

你为什么说回溯法只是“稍微”好一点呢？我没有彻底分析过它，也许你已经分析了，但我猜想这种方法比原始方法快得多。 - smendola

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- PengOne · Accepted Answer

有趣的问题; 我会尝试解答。将问题重述为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都存在解决方案，因此显然已知该问题，尽管我不一定称之为众所周知。