摘要：能以最少交换次数到达升序有序排列记为的数列记为就等价于从代表的节点在这张图中到达对应的节点的最短路径长度。上一篇质数矩阵质数矩阵下一篇唯一的序列本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解
目录
考虑：N个数字的每种排列看作是一个节点，邻节点是指能通过交换任意两个位置的数得到的新的排列。这样，所有N!个排列一个连通图。能以最少交换次数到达升序有序排列（记为B）的数列（记为A）就等价于从A代表的节点在这张图中到达B对应的节点的最短路径长度。
进一步，“交换任意两个位置的数”是可逆的操作，这是一个无向图。因此，从节点A到达节点B的最短路径长度，等于从节点B到达节点A的最短路径长度。
所以本题求解的其实就是在这种图中，从节点B点其它所有各节点的最短路径长度之和。而求最短路径长度的标准解法就是广度优先搜索。从节点B出发通过广度优先搜索遍历所有节点，记录下每个节点的层数（距离），最后求和即可。
广度优先搜索（BFS）的基本流程（即便在本系列也出现过了很多次）这里就不再赘述（不熟悉的伙伴可以参阅前面的题解）。
在一般的BFS流程中，用visited只需要记录已访问过的节点，而无需记录其对应的距离。本题解在最后统一进行距离求和，所以必须将每个节点的距离记录下来，最自然的做法当然是在visited中将节点和距离信息一起记录下来，因此在本题解中用dict()实现visited（一般只记忆节点的话用set()即可）。
# -*- coding: utf-8 -*-"""Created on Tue Sep 28 07:50:03 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 npN = 7q = deque()visited = dict()q.append((tuple(range(N)),0))visited[tuple(range(0,N))] = 0tStart = time.perf_counter()while len(q) > 0: cur,layer = q.popleft() for c2 in it.combinations(range(N), 2): nxtlst = list(cur) nxtlst[c2[0]],nxtlst[c2[1]] = nxtlst[c2[1]],nxtlst[c2[0]] nxt = tuple(nxtlst) if nxt not in visited: visited[nxt] = layer + 1 q.append((nxt,layer+1))count = 0for key in visited: count += visited[key]tCost = time.perf_counter() - tStartprint("N = {0}, count={1}, tCost = {2:6.3f}(sec)".format(N,count,tCost)) 运行结果：N = 7, count=22212, tCost = 0.073(sec)
原书还给出两个更简单的解法。
其一的思路是：某排列与最终升序排列中位置一致的数字不需要再参与交换，所以只需要找出和初始状态下的位置不同的数字进行交换就可以了。
其二的思路是利用数学上对称群的概念，通过循环置换的乘积来求解。
前一个还好理解（问题在于能不能想到这一点），后一个需要群的知识为基础。容我再学习学习品一品后再来补充题解。
上一篇：Q44: 质数矩阵
下一篇：Q46: 唯一的OX序列
本系列总目录参见：程序员的算法趣题：详细分析和Python全解
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/121525.html
摘要：可以在遍历所有矩阵时，对各种出现的次数进行计数，最后计数值为的个数即为所求结果。上一篇排序交换次数的最少化排序交换次数的最少化本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...
摘要：中的统一的终点是全白状态。比如说，的第个数恰好是，它可以由根据题设规则重排而得。上一篇填充白色填充白色下一篇优雅的地址本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 2.1 Naive Approach--正向全量搜索 ...
摘要：汉明距离可以用异或操作实现。这个问题其实可以看作是，具有个节点的全连接无向图，每条边的权重值代表两个节点所代表的数字的段码显示的二进制表示之间的汉明距离。 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述 问题：求把10个数字全部显示出来时，亮灯/灭...
摘要：但是由于不能使用作为，所以将表示状态的列表转换为后再用作的。上一篇将牌洗为逆序下一篇糖果恶作剧本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 2.1 节点状态表示 2.2 邻节点搜索 2.3 路径历史记忆以及判断邻节点是否在...
摘要：目录前言前言递推关系递推关系代码及测试代码及测试后记后记前言参见程序员的算法趣题偷懒的算盘上一篇中给出的初始方案是暴力破解或者说全量搜索的方式，总共需要搜索种情况，因此非常耗时。 目录 1. 前言 2. 递推关系 3. 代码及测试 4. 后记 1. 前言 参见程序员的算法趣...
阅读 521·2021-11-23 09:51
阅读 3347·2021-11-15 11:38
阅读 763·2021-10-14 09:42
阅读 2925·2021-09-29 09:35
阅读 1886·2021-09-03 10:33
阅读 671·2021-07-30 16:33
阅读 1381·2019-08-30 15:55
阅读 1732·2019-08-30 14:04
