目錄

1. 問題描述

2. 解題分析

2.1??Naive Approach--正向全量搜索

2.2 縮小搜索范圍

2.3 以遞歸的方式實現

2.4 反向搜索

3. 代碼及測試

4. 后記

1. 問題描述

2. 解題分析

????????把每種排序狀態看作是一個節點（共有9!=362880種狀態/節點，本系列中通常把節點和狀態交換使用），把各狀態到達“終點”狀態所需要最少重排次數視為該節點到達“終點”的距離。到此為止，本問題似乎跟Q38是完全相同類型的問題。但是，本問題與Q38相比有一個根本性的差異：不存在一個統一的終點。Q38中的統一的終點是“全白”狀態。而本問題中，從任意狀態出發，它對應的“終點”狀態是以1開始的排列，總共有8！=40320中可能的“終點”狀態！所以不能單純地像Q38那樣采樣逆向思考來解決問題。

2.1??Naive Approach--正向全量搜索

?????? 作為Na?ve approach，遍歷從每個狀態出發，然后搜索它們到某個“終點”狀態的距離（即所需重排次數），然后再進行比較。算法流程如下：

2.2 縮小搜索范圍

????????根據題設的重新排列規則，任何一個排列狀態，只要它滿足以下條件：它的第k個數恰好為k，則它肯定可以由將前k個數逆序排列得到的狀態按照題設規則重新排列而得。因此它肯定距離最遠的狀態。比如說，[1,3,4,6,5,2,7,8,9]的第5個數恰好是5，它可以由[5,6,4,3,1,2,7,8,9]根據題設規則重排而得。滿足這樣條件的排列就可以從搜索列表中排除出去，可以節省一定的搜索時間。算法流程如下：

2.3 以遞歸的方式實現

????????從任意狀態開始的搜索過程也可以用遞歸的方式實現。遞歸函數的實現流程如下：

2.4 反向搜索

????????雖然，前面說了不能像Q38那樣單純從單一狀態逆向搜索來求解。但是，畢竟可能的終點狀態數只是8!，是所有可能狀態數9！的1/9，所以從每一個可能的終點狀態進行逆向搜索還是大大縮小了搜索范圍（？）。不過事情并沒有這么簡單。正向搜索的話，雖然起點比較多，但是從起點到終點是單一路徑（即每個狀態向下一個狀態轉移是唯一的）；而反向搜索的話，則從一個狀態可能到達多個狀態（對應于正向搜索中，可能從多個狀態出發到達同一個狀態，比如說[2,1,3]和[3,2,1]根據題規則都是到達[1,2,3]）。所以反向搜索的起點數雖然少，但是從的搜索復雜度不一定比正向搜索低。定量的分析很難（超出了本渣的能力范圍），所以是騾子是馬拉出來遛一遛，不妨寫出代碼來比一比。流程如下所示：

3. 代碼及測試

# -*- coding: utf-8 -*-"""Created on Sat Sep 25 09:05:40 2021@author: chenxy"""import sysimport timeimport datetimeimport math# import randomfrom   typing import List# from   queue import Queuefrom   collections import dequeimport itertools as itimport numpy as npdef reordering1(N:int):    maxstep = 0    for start in it.permutations(range(1,N+1)):        # print(start)            ordering = list(start)        step     = 0        while ordering[0] != 1:            k = ordering[0]            # print(k)            tmp = ordering[0:k]            tmp.reverse()            ordering = tmp + ordering[k:]            step     = step + 1        if maxstep < step:            maxstep  = step            maxstart = start    return maxstep, maxstartdef reordering2(N:int):    maxstep = 0    for start in it.permutations(range(1,N+1)):                skip = False        for i in range(N):            if start[i] == i+1:                skip = True        if skip:            # Skip and go to the next.            continue            ordering = list(start)        step     = 0        while ordering[0] != 1:            k = ordering[0]            # print(k)            tmp = ordering[0:k]            tmp.reverse()            ordering = tmp + ordering[k:]            step     = step + 1        if maxstep < step:            maxstep  = step            maxstart = start    return maxstep, maxstartdef reordering3(N: int):    global maxstep    global maxstart    maxstep = 0    maxstart= None    def recur(cur, start, step):        # print(cur)        global maxstep        global maxstart        if cur[0] == 1:                        if maxstep < step:                maxstep  = step                maxstart = start                # print(cur, maxstep, maxstart)            return        k   = cur[0]        tmp = cur[0:k]        tmp.reverse()        nxt = tmp + cur[k:]        recur(nxt, start, step+1)        for start in it.permutations(range(1,N+1)):                skip = False        for i in range(N):            if start[i] == i+1:                skip = True        if skip:            # Skip and go to the next.            continue        start = list(start)        recur(start, start, 0)    return maxstep, maxstartdef reordering4(N: int):    maxstep = 0    maxstart= None        for start in it.permutations(range(1,N+1)):                if start[0] != 1:            # Skip and go to the next.            continue        # For each one of them, perform BFS to find the max distance.        visited   = set()        q         = deque()        q.append((start,0))        visited.add(start)                    while len(q) > 0:            cur, step = q.popleft()                # print(cur,step)            for k in range(1,N):                # Search for the next state                 if cur[k] == k+1:                    tmp = list(cur[0:k+1])                    tmp.reverse()                    nxt = tuple(tmp + list(cur[k+1:]))                    if nxt not in visited and nxt[0]!=1:                        visited.add(nxt)                        q.append((nxt,step+1))                if maxstep < step:            maxstep = step            # maxstart = start            maxstart = cur # In reverse search, the final state corresponds to the start in forward search        return maxstep, maxstart

if __name__ == "__main__":         N = 9    tStart = time.perf_counter()    maxstep,maxstart = reordering1(N)    tCost  = time.perf_counter() - tStart    print("N={0}, maxstep = {1}, maxstart = {2}, tCost = {3:6.3f}(sec)".format(N,maxstep,maxstart,tCost))    tStart = time.perf_counter()    maxstep,maxstart = reordering2(N)    tCost  = time.perf_counter() - tStart    print("N={0}, maxstep = {1}, maxstart = {2}, tCost = {3:6.3f}(sec)".format(N,maxstep,maxstart,tCost))                    tStart = time.perf_counter()    maxstep,maxstart = reordering3(N)    tCost  = time.perf_counter() - tStart    print("N={0}, maxstep = {1}, maxstart = {2}, tCost = {3:6.3f}(sec)".format(N,maxstep,maxstart,tCost))                                    tStart = time.perf_counter()    maxstep,maxstart = reordering4(N)    tCost  = time.perf_counter() - tStart    print("N={0}, maxstep = {1}, maxstart = {2}, tCost = {3:6.3f}(sec)".format(N,maxstep,maxstart,tCost))            

?????????運行結果：

4. 后記

????????4種實現方式的運行時間居然沒有什么顯著的差異。

? ? ? ? 不過，寫多種解法本身也是一種很有益的聯系。

? ? ? ? 當然，這個問題是不是還有更高效的解決方案是一個開放的問題，還有待進一步琢磨。

???????

? ? ? ? 上一篇：Q38: 填充白色

? ? ? ? 下一篇：Q40: 優雅的IP地址????

? ? ? ?本系列總目錄參見：程序員的算法趣題：詳細分析和Python全解