程序员的算法趣题Q39: 反复排序

1. 问题描述

2. 解题分析

把每种排序状态看作是一个节点（共有9!=362880种状态/节点，本系列中通常把节点和状态交换使用），把各状态到达“终点”状态所需要最少重排次数视为该节点到达“终点”的距离。到此为止，本问题似乎跟Q38是完全相同类型的问题。但是，本问题与Q38相比有一个根本性的差异：不存在一个统一的终点。Q38中的统一的终点是“全白”状态。而本问题中，从任意状态出发，它对应的“终点”状态是以1开始的排列，总共有8！=40320中可能的“终点”状态！所以不能单纯地像Q38那样采样逆向思考来解决问题。

2.1Naive 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 sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
from   collections import deque
import itertools as it
import numpy as np

def 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, maxstart

def 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, maxstart

def 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, maxstart

def 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种实现方式的运行时间居然没有什么显著的差异。

不过，写多种解法本身也是一种很有益的联系。

当然，这个问题是不是还有更高效的解决方案是一个开放的问题，还有待进一步琢磨。