“块移动”问题解答
相关链接：
http://blog.programet.cn/2008/09/blog-post_6768.html
http://www.brand.site.co.il/riddles/200809a.html
我们需要ceil((n+1)/2) 次块移动来完成整个排序（不考虑n=1或2的情况）。
当n是奇数，我们每一步都把从n这个数到最后一个数的中间的那个数k和它后面那个数k-1移动到数n的前面。下面是n=7的例子：
原始状态
[4, 3, 7, 6, 5, 2, 1]
将 4和3 移动到 7 的前面 现在位于7和1中间的数是5
[4, 5, 2, 3, 7, 6, 1]
将 5和2 移动到 7 的前面 现在位于7和1中间的数是6
[4, 5, 6, 1, 2, 3, 7]
将 6和1 移动到 7 的前面 现在7处于最后一位
[1, 2, 3, 4, 5, 6, 7]
将 123 移动到 456 前面 完成移动
下面证明当n>=3时是成立的。对于每一个位置上的数，我们考察它后面那个数是否小于他（也就是逆序对的意思……囧）。同样会有“顺序对”的概念（只限于相邻的数）。我们希望将顺序对的数目从0提高到n-1，这样我们的目的也就达到了。在我们的那些移动中，每一步都改变了3个元素的后续元素。这看起来每一步都能增加3个顺序对，但是很容易能得出：实际上每一步都不能增加超过2个顺序对。
这样，我们就已经给出了一个ceil((n-1)/2)的算法。之所以需要额外的一步是因为第一部和最后一步最多增加1个顺序对。
证毕。
P.S:
当n=13时，下面这个序列需要的移动次数比完全逆序还要多！[4 3 2 1 5 13 12 11 10 9 8 7 6]这是第一个被发现具有这样性质的序列。 现在已经证明，对于所有从13开始往后的奇数n，都存在一个比完全逆序的移动次数要多的序列。下面是相关论文：
H. Eriksson, K. Eriksson, J. Karlander, L. Svensson and J. Wästlund,Sorting a bridge hand, Discrete Math 241:289–300, 2001.
以及下文的第十个定理：
Isaac Elias, Tzvika Hartman, “A 1.375-Approximation Algorithm for Sorting by Transpositions,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 3, no. 4, pp. 369-379, Oct-Dec, 2006.
本文由 严酷的魔王 创作，转载或引用前请联系我们。
相关文章：
标签：策略, 算法, 组合, 证明, 趣题
这个解法好不爽。。。。。
回复