1. 这是一个只需要五次交换的解决方案，用于
9 8 7 1 4 3 5 6 2 (1,9): 2 8 7 1 4 3 5 6 9 (2,7): 2 5 7 1 4 3 8 6 9 (2,4): 2 1 7 5 4 3 8 6 9 (3,8): 2 1 6 5 4 3 8 7 9 (3,6): 2 1 3 5 4 6 8 7 9
2. 对于这个初始配置
3 5 6 7 8 1 9 2 4
六次交换就足够了。这是一个将其置于 1-away 配置的方法
3 5 6 7 8 1 9 2 4 (5,9): 3 5 6 7 4 1 9 2 8 (4 和 8 现在足够接近了。) (1,3): 6 5 3 7 4 1 9 2 8 (1,6): 1 5 3 7 4 6 9 2 8 (4、8、1、3 和 6 现在足够接近了) (2,4): 1 7 3 5 4 6 2 9 8 (7,8): 1 7 3 5 4 6 2 9 8 (2,7): 1 2 3 5 4 6 7 9 8 你能做得更好吗？
关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻事业： 订阅。通过购买订阅，您正在帮助确保未来能够继续讲述关于塑造我们当今世界的发现和思想的具有影响力的故事。
3. 这是一个九个项目的非常糟糕的初始配置
8 9 1 2 3 4 5 6 7.
每个元素都与其正确位置相差两个位置。每次交换最多只能将一个雕塑移动到其正确位置。然而，一旦前七个雕塑就位，最后两个雕塑将只相差一个位置，因此七步是最坏的情况。
4. 全能启发式专家 Tom Rokicki 提出了以下精美的解决方案（我的同事 Richard Cole 和数学家 Ivan Rezanka 有类似的直觉）。
当目标是实现 d-away 配置时，一个最坏的初始配置是从有序配置开始进行 d+1 旋转。例如，当 d = 1 时，配置
8 9 1 2 3 4 5 6 7 是一个 2 旋转。相比之下，对 9 个元素进行 6 旋转（当目标是实现 5-away 配置时，用于最大化交换次数）会产生
4 5 6 7 8 9 1 2 3
Rokicki 观察到，将会有 n-(d+1) 个数字至少偏离了 d+1 个位置（在 6 旋转示例中为 1、2、3），所有数字都在同一方向上。每次交换只能将这些数字中的一个移动到其位置范围内。
实际上，按顺序将它们交换到位（对于此示例，将位置 7 的 1 与位置 1 的 4 交换，然后将位置 8 的 2 与位置 2 的 5 交换，依此类推）实际上是最佳解决方案。
事实上，无论从哪个初始配置开始，都可以先将 1 交换到位，然后是 2，然后是 3，依此类推，直到最大的 d+1 个雕塑。最后那些雕塑与其正确位置的距离不超过 d。
5. 对于 n 个元素，有多少个 1-away 配置？
回顾一下似乎在许多数学领域中出现的斐波那契数列
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
每个数字都是前两个数字的和，即 fib(k+2) = fib(k+1) + fib(k)。让我们通过它们在该列表中的位置来识别这些数字，因此 fib(0) = fib(1) = 1，fib(6) = 13（请记住我们从 0 开始），依此类推。
那么，n 个元素的 1-away 排列（包括完全排序的排列）的数量就是 fib(n)。
对于 n = 1，显然只有一个 (fib(1))。
对于 n = 2，有两个：1 2 和 2 1。
对于 n = 3，有三个：1 2 3；1 3 2；2 1 3
对于 n = 4，有五个：三个涉及 2 3 4，其中 1 固定；然后交换 1 和 2，并且有 3 和 4 的两种排列。
一般来说，对于长度为 n 且第一个雕塑就位的排列，有 fib(n-1) 个。如果第一个雕塑不在位，则它必须在位置 2，但这表示第二个雕塑必须在位置 1（没有其他元素可以在位置 1）。因此，这固定了前两个位置的乱序。现在，最后 n-2 个雕塑有 fib(n-2) 个排列。
最后一个结果最初是在以下写得很好的文章（法语）中发现的，您可以在网上找到
“Quelques resultats dans la metrique des permutations”，作者：Rene Lagrange，Annales scientifiques de l'E.N.S. 第三辑，第 79 卷，第 3 期，1962 年，第 199-241 页。
http://archive.numdam.org/article/ASENS_1962_3_79_3_199_0.pdf