资讯专栏INFORMATION COLUMN

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

gitmilk / 1061人阅读

摘要:中的统一的终点是全白状态。比如说,的第个数恰好是,它可以由根据题设规则重排而得。上一篇填充白色填充白色下一篇优雅的地址本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解

目录

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全解

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/121126.html

相关文章

  • 序员算法趣题Q45: 排序交换次数最少化

    摘要:能以最少交换次数到达升序有序排列记为的数列记为就等价于从代表的节点在这张图中到达对应的节点的最短路径长度。上一篇质数矩阵质数矩阵下一篇唯一的序列本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 ...

    flybywind 评论0 收藏0
  • 序员算法趣题Q46: 唯一OX序列

    摘要:可以在遍历所有矩阵时,对各种出现的次数进行计数,最后计数值为的个数即为所求结果。上一篇排序交换次数的最少化排序交换次数的最少化本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...

    y1chuan 评论0 收藏0
  • 序员算法趣题Q54: 偷懒算盘

    摘要:且听下回分解基于动态规划策略的优化解法参见程序员的算法趣题偷懒的算盘上一篇程序员的算法趣题同数包夹程序员的算法趣题同数包夹本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述   ...

    wangzy2019 评论0 收藏0
  • 序员算法趣题Q22: 不缠绕纸杯电话

    摘要:假设有几个小朋友以相同间隔围成圆周,要结对用纸杯电话相互通话。如果绳子交叉,很有可能会缠绕起来,所以结对的原则是不能让绳子交叉。如下所示运行结果上一篇异或杨辉三角形下一篇禁止右转本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问...

    MoAir 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<