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

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. 后记

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

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

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

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