输出《傻子排序法》

pusofalse

书架的某一层里放了一套百科全书，可是它们的顺序是乱的，一个傻子想将它们排好顺序，也就是让书的顺序从左至右依次是第1卷、第2卷、第3卷、、、第n卷。他排序的方法是这样的：不断从最右边取出一本不在原位的书，将它放入它该在的位置上。比如：

书的初始顺序是这样的：卷3、卷1、卷2、卷4
初始序列： 3 1 2 4
最右边的不在原位的书是卷2，所以傻子将2取出，将它放入左起第1本书的右边，于是书的顺序就变成了：
第一步：3 2 1 4
此时卷2处在了它该在的位置上。傻子继续从最右边取书，新的顺序变成了：
第二步：1 3 2 4
此时卷1处在了它该在的位置上，但第1步中，已经就位的2却被挤到了左起第3的位置上。
第三步： 、、、

这种排序法很可能捡了芝麻，丢了西瓜，为了一本书的位置而破坏掉一连串原已排好的书，可谓是鼠目寸光，缺乏远见。
但出人意料的是，这种看上去明显有漏洞的排序法竟然是一种正确的排序算法——对于任意一个初始序列，采用这种方法总能让序列最终变得有序。为了证明这一点，我们按照如下方式把序列编码为 n 位的 01 串：左起第 i 位为 1 当且仅当第 i 卷在正确的位置上。上例中序列3124就被编码为0001，因为在这4本书中，只有卷4在正确的位置上。
如果某一次操作中，傻子把第 k 卷放进了正确的位置，那么考虑所有卷数小于 k 的书：如果它原本就在左起第 k 本书的左边，这个操作影响不到它；如果它原本就是左起第 k 本或者更右边的书（这表明它原本就不在正确的位置上），那么现在它仍然不可能在正确的位置上（它的位置只可能不变或者更靠右了）。因此，编码的前 k-1 位是不动的，但第 k 位从 0 变成 1 了。这就意味着，任意一个操作总会让整个二进制编码变大。而容易看出，只要序列不是有序的，傻子总有可以操作的对象，因此序列编码将不断增加，最终将变成 11...1。此时所有书都在它应该在的位置上，整个序列也就有序了。

傻子的每一次操作，编码的变化如下：
0-> 3124  -> 0001
1-> 3214  -> 0101
2-> 1324  -> 1001
3-> 1234  -> 1111

问题：AU3编程输出傻子排序法，给定初始序列912345678，或任意初始序列，输出傻子排序的详细步骤。
效率：<= 50ms。

PS：“傻子排序”其实是今年1月和2月的 UyHiP 谜题之一，Michael Brand 详细地讨论了这个问题，有兴趣的朋友可以看看：
http://www.brand.site.co.il/riddles/201001q.html
http://www.brand.site.co.il/riddles/201002q.html

xsjtxy

这样行不行？

$i1 = "91234567809123456780912345678091234567809123456780912345678091234567809123456780"
$i2 = ""
$i3 = 0
While 1
$i4 = StringInStr($i1, $i3)
if $i4 <> 0 then
$i5 = StringLeft($i1, $i4)
$i6 = StringTrimLeft($i1, $i4)
$i2 = $i2&StringRight($i5, 1)
$i7 = StringTrimRight($i5, 1)
$i1 = $i6&$i7
ContinueLoop
endif

if $i3 = 9 then exitloop
$i3 = $i3 + 1
WEnd
msgbox(0,"",$i2)

xsjtxy

用时1豪秒

$begin = TimerInit()
$i1 = "3215345679831324654897358231545872335575375240147688961353"
$i2 = ""
$i3 = 0
While 1
$i4 = StringInStr($i1, $i3)
if $i4 <> 0 then
$i5 = StringLeft($i1, $i4)
$i6 = StringTrimLeft($i1, $i4)
$i2 = $i2&StringRight($i5, 1)
$i7 = StringTrimRight($i5, 1)
$i1 = $i6&$i7
ContinueLoop
endif

if $i3 = 9 then exitloop
$i3 = $i3 + 1
WEnd
msgbox(0,"用时"&TimerDiff($begin)&"毫秒!",$i2)

xsjtxy

是不是我理解错了？

pusofalse

回复 2# xsjtxy

xsjtxy兄好像理解错了。
给定初始序列912345678，输出傻子排序步骤，如下：
1        912345678
2        912345687
3        912345768
4        ... ...
5        ... ...
... ... ... ...
... ... ... ...
n        123456789

感谢参与！

xsjtxy

这样呢？

#include <Array.au3>
$begin = TimerInit()
$i1 = "987654321"
$i2 = ""
$i3 = 0
dim $i8
dim $avArray[1]
_ArrayAdd($avArray,$i1)
While 1
$i4 = StringInStr($i1, $i3)
if $i4 <> 0 then
$i5 = StringLeft($i1, $i4)
$i6 = StringTrimLeft($i1, $i4)
$i7 = StringTrimRight($i5, 1)
$i1 = $i6&$i7
$i2 = $i2&StringRight($i5, 1)
if $i8 <> $i2&$i6&$i7 then _ArrayAdd($avArray,$i2&$i6&$i7)
$i8 = $i2&$i6&$i7
ContinueLoop
endif

if $i3 = 9 then exitloop
$i3 = $i3 + 1
WEnd
$t = TimerDiff($begin)
_ArrayDisplay($avArray,"用时"&StringLeft($t,StringInStr($t, ".")+2)&"毫秒!")

pusofalse

回复 6# xsjtxy


    初始序列使用987654321，xsjtxy兄的结果是正确的，但改为912345678之后就不对了，傻子是从最右边取书的。

使用912345678，xsjtxy的结果如下：
[1] 912345678
[2] 123456789
结果变成了直接从最左边取第9卷，将它放入了原位。虽然这样能够将书排好，但傻子不知道竟然还有如此简单的方法。

xsjtxy

我当时就哭了

大绯狼

$time = TimerInit()
Dim $before = 912345678
$num = StringSplit($before, "")
While 1
        For $i = $num[0] To 1 Step -1
                If $num[$i] <> $i Then
                        $temp= $num[$num[$i]]
                         $num[$num[$i]]=$num[$i]
                         $num[$i]=$temp
                        ContinueLoop 2
                EndIf
        Next
        MsgBox(0, 0, TimerDiff($time))
        ExitLoop
WEnd
$msg=""
For $i= 1 To $num[0]
        $msg&=$num[$i]
Next
MsgBox(0,0,"排序后序列:"&$msg)

纯粹排序。。。。。。没有优化 但是 时间上完全没有任何问题 应该考虑给个复杂点的序列

pusofalse

回复 9# 大绯狼


    - -||| 最重要的是要输出步骤，这个被你无视了~

大绯狼

Dim $out[1]
$out[0] = 0
$time = TimerInit()
Dim $before = 912345678
$num = StringSplit($before, "")
While 1
        For $i = $num[0] To 1 Step -1
                If $num[$i] <> $i Then
                        $temp = $num[$num[$i]]
                        $num[$num[$i]] = $num[$i]
                        $num[$i] = $temp
                        ReDim $out[UBound($out) + 1]
                        $msg = ""
                        For $i = 1 To $num[0]
                                $msg &= $num[$i]
                        Next
                        $out[0] += 1
                        $out[UBound($out) - 1] = $msg
                        ContinueLoop 2
                EndIf
        Next
        $endtime = TimerDiff($time)
        ExitLoop
WEnd
$msg = ""
For $i = 1 To $out[0]
        $msg &= "["&$i&"]"&$out[$i] & @CR
Next
MsgBox(0, 0, "排序:" & $out[0] & "次"&@CRLF&"排序过程:"&@CRLF&$msg&@CRLF&"用时:"&$endtime)

好嘛。。。。。。。。。加上了 不过悲剧的是输出过程浪费了1MS的时间。。。。

pusofalse

回复 11# 大绯狼


效率很强大，但排序步骤有问题，请看：

排序:8次
排序过程:
[0]912345678 ; 这个是我加的
[1]912345687
[2]912345786
[3]912346785
[4]912356784
[5]912456783
[6]913456782
[7]923456781
[8]123456789

[0]是初始序列，是我自己加上去的。
[1]是没问题的，最右边的卷8在卷9的位置上，移到左起第8的位置，卷8得位，卷7成了第9位。
[2]出现问题了，最右边的卷7不在其位，所以移到左起第7的位置上，此时序列应该变成912345768，而不是912345786。这第2步的操作会将先前排好的卷8再次挤到卷9的位置，这也是有趣的地方所在。
以下步骤同是，之后的某一次操作可能会将原先已经排好的书挤到更右边去。如1#所说：这种排序法很可能捡了芝麻，丢了西瓜，为了一本书的位置而破坏掉一连串原已排好的书，可谓是鼠目寸光，缺乏远见。
此题的目的就是要输出这样的一种排序算法，而不管这种排序法究竟效率如何。

大绯狼

回复 12# pusofalse


考虑不周啊 我继续

3mile

我很笨，别笑我。

#include <array.au3>

;$str = "912345678"
Local $time=TimerInit()
$str="913245678"
$len=StringLen($str)
Local $arr_n[$len+1][2], $temp[$len+1]
For $n = 1 To $len
        $arr_n[$n][0] = $n
        $arr_n[$n][1] = StringMid($str, $n, 1)
Next
aa()
_ArrayDisplay($arr_n,TimerDiff($time))
Func aa()
        For $i = $len To 1 Step -1
                If $arr_n[$i][0] = $arr_n[$i][1] Then
                        $temp[$i] = 1
                        ContinueLoop
                Else
                        $temp[$i] = 0
                EndIf
        Next
        ;_ArrayDisplay($temp)
        $numswap = _ArrayFindAll($temp, '0')
        If @error Then Return
        If UBound($numswap) > 1 Then
                $sw1 = $numswap[UBound($numswap) - 1]
                $sw2 = $numswap[UBound($numswap) - 2]
                _ArraySwap($arr_n[$sw1][1], $arr_n[$sw2][1])
                aa()
        EndIf
EndFunc   ;==>aa

没注意到要输出步骤，上面的仅作运行时间参考。
下面的有输出步骤：

#include <array.au3>

$str = "912345678"
Local $time=TimerInit()
;$str="913245678"
$len=StringLen($str)
Local $arr_n[$len+1][2], $temp[$len+1],$output[10],$tempstr
Local $z=0
For $n = 1 To $len
        $arr_n[$n][0] = $n
        $arr_n[$n][1] = StringMid($str, $n, 1)
Next
aa()
_ArrayDisplay($arr_n,TimerDiff($time))
_ArrayDisplay($output,"输出步骤")
Func aa()
        For $i = $len To 1 Step -1
                If $arr_n[$i][0] = $arr_n[$i][1] Then
                        $temp[$i] = 1
                        ContinueLoop
                Else
                        $temp[$i] = 0
                EndIf
        Next
        ;_ArrayDisplay($temp)
        $numswap = _ArrayFindAll($temp, '0')
        If @error Then Return
        If UBound($numswap) > 1 Then
                $sw1 = $numswap[UBound($numswap) - 1]
                $sw2 = $numswap[UBound($numswap) - 2]
                _ArraySwap($arr_n[$sw1][1], $arr_n[$sw2][1])
                $tempstr=''
                For $y=1 To 9
                        $tempstr&=$arr_n[$y][1]
                Next
                $output[$z]=$tempstr
                $z+=1
                aa()
        EndIf
EndFunc   ;==>aa

pusofalse

回复 14# 3mile


    3mile兄貌似也理解错了，请参考11#的输出结果及12#的分析。感谢参与！