程序员的算法趣题|程序员的算法趣题Q39: 反复排序 python|广度优先|启发式算法|递

目录

1. 问题描述
2. 解题分析
2.1Naive Approach--正向全量搜索
2.2 缩小搜索范围
2.3 以递归的方式实现
2.4 反向搜索
3. 代码及测试
4. 后记
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 fromtyping import List # fromqueue import Queue fromcollections import deque import itertools as it import 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. continueordering = 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 searchreturn 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全解
【程序员的算法趣题|程序员的算法趣题Q39: 反复排序】