目錄

1. 問(wèn)題描述

2. 解題分析

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

2.2 縮小搜索范圍

2.3 以遞歸的方式實(shí)現(xiàn)

2.4 反向搜索

3. 代碼及測(cè)試

4. 后記

1. 問(wèn)題描述

2. 解題分析

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

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

?????? 作為Na?ve approach，遍歷從每個(gè)狀態(tài)出發(fā)，然后搜索它們到某個(gè)“終點(diǎn)”狀態(tài)的距離（即所需重排次數(shù)），然后再進(jìn)行比較。算法流程如下：

2.2 縮小搜索范圍

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

2.3 以遞歸的方式實(shí)現(xiàn)

????????從任意狀態(tài)開(kāi)始的搜索過(guò)程也可以用遞歸的方式實(shí)現(xiàn)。遞歸函數(shù)的實(shí)現(xiàn)流程如下：

2.4 反向搜索

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

3. 代碼及測(cè)試

# -*- 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))            

?????????運(yùn)行結(jié)果：

4. 后記

????????4種實(shí)現(xiàn)方式的運(yùn)行時(shí)間居然沒(méi)有什么顯著的差異。

? ? ? ? 不過(guò)，寫(xiě)多種解法本身也是一種很有益的聯(lián)系。

? ? ? ? 當(dāng)然，這個(gè)問(wèn)題是不是還有更高效的解決方案是一個(gè)開(kāi)放的問(wèn)題，還有待進(jìn)一步琢磨。

???????

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

? ? ? ? 下一篇：Q40: 優(yōu)雅的IP地址????

? ? ? ?本系列總目錄參見(jiàn)：程序員的算法趣題：詳細(xì)分析和Python全解