顺排序变成逆排序的问题（段位制的编辑）

noski

在外面看这个贴子名字好久了，竟然一直以为是段位制，昨天才发现这是一道有趣的题。。
总结一下之前的：

金眼睛：
          N=2    N=3    N=4    N=5    N=6    N=7    N=8    N=9    N=10    N=11    N=12    N=13
情况数    1      4      10     20     35     56     84     120    165     220     286     364

ares_g：
20楼8步的解法；
顺便补充一下：
1个数0步；
2个数1步；
3个书2步；
4个数3步；
5个数3步；
6个数4步；
7个数4步；
8个数5步。
-------------------------------------------------

我又继续往下算了一下：
1个数0步，0
2个数1步，1种解法；
3个数2步，4种解法；
4个数3步，40种解法；
5个数3步，2种解法；
6个数4步，112种解法；
7个数4步，8种解法；
8个数5步，720种解法；
9个数5步，10种解法；
10个数6步，？种解法；
11个数?步，？
12个数?步，？
13个数?步，？

9个数和10个数是刚刚算的，10个数6步的解法总数没算出来，但找到答案了，而且也证明10个数5步是解决不了的。
研究上述的规律发现：2N个数字需要的步数比2N-1个数字的步数多1；奇数个数字的解法都很少，偶数个数字的解法则多得多。
下面是我的推理：
1. 当数字个数为 2N+1 时，解法的数量虽少，但仍有递增的趋势；
2. 当数字为 2N 时，解法的数量很多，但也是递增的趋势；
3. 由此假设：2N+1 个数字的解法数量总比 2N 个数字的解法数少；
4. 2N 个数字的解法总数比 2N-1 的多很多，可以理解为：2N 个数任意取两个数绑在一块，用 2N-1 的解法来做，最后加一步交换两个绑在一起的；
5. 2N+1 个数字的最小步数如果比 2N 个数字的最小步数多 1，那么 2N+1 个数字的解法数必比 2N 个数的解法多很多；
6. 由5和3的假设矛盾，得出 2N+1 个数字的最小步数与 2N 个数字的最小步数相同；
7. 结论：11个数需要6步，12个数需要7步，13个数需要7步。。

贴一个9个数字的5步解法：
1 2 3 4 5 6 7 8 9
3 4 5 6 1 2 7 8 9
3 2 7 8 9 4 5 6 1
9 4 3 2 7 8 5 6 1
9 8 5 4 3 2 7 6 1
9 8 7 6 5 4 3 2 1
而10个数字的6步解法把1和2绑在一起用这个方法就行了。

[ 本帖最后由 noski 于 2009-5-29 14:57 编辑 ]

noski

事实证明，我的推断是正确的。

9个数字的5步方法：
1 2 3 4 5 6 7 8 9
3 4 5 6 1 2 7 8 9
3 2 7 8 9 4 5 6 1
9 4 3 2 7 8 5 6 1
9 8 5 4 3 2 7 6 1
9 8 7 6 5 4 3 2 1

11个数字的6步方法：
1 2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 1 2 8 9 10 11
3 2 8 9 10 11 4 5 6 7 1
11 4 3 2 8 9 10 5 6 7 1
11 10 5 4 3 2 8 9 6 7 1
11 10 9 6 5 4 3 2 8 7 1
11 10 9 8 7 6 5 4 3 2 1

13个数字的7步方法：
1 2 3 4 5 6 7 8 9 10 11 12 13
3 4 5 6 7 8 1 2 9 10 11 12 13
3 2 9 10 11 12 13 4 5 6 7 8 1
13 4 3 2 9 10 11 12 5 6 7 8 1
13 12 5 4 3 2 9 10 11 6 7 8 1
13 12 11 6 5 4 3 2 9 10 7 8 1
13 12 11 10 7 6 5 4 3 2 9 8 1
13 12 11 10 9 8 7 6 5 4 3 2 1


果然暴力穷举不靠谱，画来画去还是在纸上找到了规律，哈哈，你看出来了吗？

1. 先把1和2移到后面数字的中间（由于除了1、2剩奇数个数字，所以前一半要比后一半多一个，中间插入1、2）。

2. 接着把2和以后的部分移到3之后。

3. 好了，一对一对的往前挪直到全部解决。

因此，所有2N-1个数字从正序到逆序的最小步数都是N。

[ 本帖最后由 noski 于 2009-5-29 15:02 编辑 ]

noski

2N+1个数字，按上面的规律，N+1步必能完成。
但这个解法不是每次移动N个，只有第二步是移动N个，其它步都是移动2个。
我不能完全肯定这就是最小步，但这个方法的效率还挺高的，一次正好排好两个。
＝＝＝＝＝
嗯嗯，莫非俺神经，认为Good Shoes＝鼓捣数字。。

[ 本帖最后由 noski 于 2009-5-29 15:05 编辑 ]

noski

对，的确可以看成是N个，那么这样编程会容易一点吧。不知各种程序语言函数库中的逆序函数，有没有这个效率高。<BR>
不过，数字过大时会让人感觉不够好。比如我有201个数字，那么N＝100。你的说法是每次都挪100个数字，挪101次；而我的说法是只有一次需要挪100个数字，其余100次只要每次挪两个数字。当然两个实质是一回事。要是用链表的话，就打断再接上就行了。。

noski

赞！这样一来规律性就更强了，一下子就能看出来移动的目的。<BR>
先前后颠倒，再两个两个解决。你17楼说的函数flipud()的算法，不知有没有这个高效

noski

我这样想的：要是可以把数字的乱序度看成“熵”一样的话，比如设定一个数字其后面有几个比它大的，熵就加几。那么题中从正序到逆序，就是最乱的情况。所以N个随机打乱的数字排序的最少步数最多也就是33#那么多。