目录

1. 问题描述

2. 解题分析

3. 代码及测试

4. 后记

---

1. 问题描述

 

2. 解题分析

        考虑：N个数字的每种排列看作是一个节点，邻节点是指能通过交换任意两个位置的数得到的新的排列。这样，所有N!个排列一个连通图。能以最少交换次数到达升序有序排列（记为B）的数列（记为A）就等价于从A代表的节点在这张图中到达B对应的节点的最短路径长度。

        进一步，“交换任意两个位置的数”是可逆的操作，这是一个无向图。因此，从节点A到达节点B的最短路径长度，等于从节点B到达节点A的最短路径长度。

        所以本题求解的其实就是在这种图中，从节点B点其它所有各节点的最短路径长度之和。而求最短路径长度的标准解法就是广度优先搜索。从节点B出发通过广度优先搜索遍历所有节点，记录下每个节点的层数（距离），最后求和即可。

        广度优先搜索（BFS）的基本流程（即便在本系列也出现过了很多次）这里就不再赘述（不熟悉的伙伴可以参阅前面的题解）。

        在一般的BFS流程中，用visited只需要记录已访问过的节点，而无需记录其对应的距离。本题解在最后统一进行距离求和，所以必须将每个节点的距离记录下来，最自然的做法当然是在visited中将节点和距离信息一起记录下来，因此在本题解中用dict()实现visited（一般只记忆节点的话用set()即可）。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Tue Sep 28 07:50:03 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

N       = 7
q       = deque()
visited = dict()
q.append((tuple(range(N)),0))
visited[tuple(range(0,N))] = 0

tStart = 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 = 0
for key in visited:
    count += visited[key]
tCost = time.perf_counter() - tStart
print('N = {0}, count={1}, tCost = {2:6.3f}(sec)'.format(N,count,tCost)) 

        运行结果：N = 7, count=22212, tCost =  0.073(sec)

4. 后记

        原书还给出两个更简单的解法。

        其一的思路是：某排列与最终升序排列中位置一致的数字不需要再参与交换，所以只需要找出和初始状态下的位置不同的数字进行交换就可以了。

        其二的思路是利用数学上对称群的概念，通过循环置换的乘积来求解。

        前一个还好理解（问题在于能不能想到这一点），后一个需要群的知识为基础。容我再学习学习品一品后再来补充题解。

        上一篇：Q44: 质数矩阵

        下一篇：

        本系列总目录参见：程序员的算法趣题：详细分析和Python全解