要把書(shū)架上的圖書(shū)依序整理好是件繁瑣的工作，因此圖書(shū)館管理員很想知道最有效率的做法。她發(fā)現(xiàn)將書(shū)按照順序排列的最好方法就是每次調(diào)換兩本書(shū)。也就是說(shuō)，每次取下兩本書(shū)，交換次序后再擺回書(shū)架。
她需要交換幾次，才能將上圖所示的整套百科全書(shū)排成123456789的次序？
如果書(shū)的次序是457681923，怎樣做才是最有效率的？
請(qǐng)?jiān)O(shè)計(jì)一套策略，不論百科全書(shū)的次序如何，都可以找出應(yīng)該如何交換的最佳整理方法。
解答與分析
所需交換的次數(shù)，與書(shū)本次序的混亂程度有關(guān)，以下說(shuō)明該如何系統(tǒng)地予以分析。首先，將書(shū)本要求的次序列在原有次序之上：
要求次序 1 2 3 4 5 6 7 8 9
原有次序 6 5 7 1 8 9 3 2 4
這樣就可以清楚地看出3和7正好是在對(duì)方的位置，因此只要將兩者調(diào)換，以(3 7)表示，就可以使它們各在其位。
其他的書(shū)就不是這樣單純的擺錯(cuò)位置。稍加觀察，我們會(huì)發(fā)現(xiàn)：
6是在1的位置
1是在4的位置
4是在9的位置
9是在6的位置
因此這4本書(shū)只須彼此互換即可。它們的相對(duì)關(guān)系可以用(6 1 4 9)表示，最少需要3次交換，先是(4 9)，之后(1 4)，最后(6 1)。
同理，剩下的3本書(shū)的相對(duì)關(guān)系也可以用(5 2 8)表示，因?yàn)椋?/p>
5是在2的位置
2是在8的位置
8是在5的位置
所以可以經(jīng)過(guò)(2 8)之后再做(5 2)的交換，把書(shū)全都放回到正確位置。
因此，圖上的百科全書(shū)可以經(jīng)過(guò)以下的交換，恢復(fù)到正確的次序：
(3 7)(4 9)(1 4)(6 1)(2 8)(5 2)
這并不是唯一的答案，不過(guò)從原有的次序至少須經(jīng)過(guò)6次交換才能完成整理工作。將同樣的方法應(yīng)用到第二種次序：
要求次序 2 3 4 5 6 7 8 9
原有次序 4 5 7 6 8 1 9 2 3
我們可以用
(4 1 6)(5 2 8)(7 3 9)
來(lái)描述原有次序的混亂程度。而這些相對(duì)關(guān)系可以經(jīng)過(guò)下列的6次交換恢復(fù)到正確的次序：
(1 6)(4 1)(2 8)(5 2)(3 9)(7 3)
請(qǐng)找出需要幾次交換才能把原有次序?yàn)? 3 5 9 4 1 8 6 7的書(shū)整理好。
