程序員的算法趣題Q45: 排序交換次數(shù)的最少化

flybywind 發(fā)布于2021-09-29 09:35 / 3189人閱讀

摘要：能以最少交換次數(shù)到達(dá)升序有序排列記為的數(shù)列記為就等價(jià)于從代表的節(jié)點(diǎn)在這張圖中到達(dá)對(duì)應(yīng)的節(jié)點(diǎn)的最短路徑長(zhǎng)度。上一篇質(zhì)數(shù)矩陣質(zhì)數(shù)矩陣下一篇唯一的序列本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解

1. 問(wèn)題描述

2. 解題分析

3. 代碼及測(cè)試

4. 后記

1. 問(wèn)題描述

2. 解題分析

????????考慮：N個(gè)數(shù)字的每種排列看作是一個(gè)節(jié)點(diǎn)，鄰節(jié)點(diǎn)是指能通過(guò)交換任意兩個(gè)位置的數(shù)得到的新的排列。這樣，所有N!個(gè)排列一個(gè)連通圖。能以最少交換次數(shù)到達(dá)升序有序排列（記為B）的數(shù)列（記為A）就等價(jià)于從A代表的節(jié)點(diǎn)在這張圖中到達(dá)B對(duì)應(yīng)的節(jié)點(diǎn)的最短路徑長(zhǎng)度。

????????進(jìn)一步，“交換任意兩個(gè)位置的數(shù)”是可逆的操作，這是一個(gè)無(wú)向圖。因此，從節(jié)點(diǎn)A到達(dá)節(jié)點(diǎn)B的最短路徑長(zhǎng)度，等于從節(jié)點(diǎn)B到達(dá)節(jié)點(diǎn)A的最短路徑長(zhǎng)度。

????????所以本題求解的其實(shí)就是在這種圖中，從節(jié)點(diǎn)B點(diǎn)其它所有各節(jié)點(diǎn)的最短路徑長(zhǎng)度之和。而求最短路徑長(zhǎng)度的標(biāo)準(zhǔn)解法就是廣度優(yōu)先搜索。從節(jié)點(diǎn)B出發(fā)通過(guò)廣度優(yōu)先搜索遍歷所有節(jié)點(diǎn)，記錄下每個(gè)節(jié)點(diǎn)的層數(shù)（距離），最后求和即可。

????????廣度優(yōu)先搜索（BFS）的基本流程（即便在本系列也出現(xiàn)過(guò)了很多次）這里就不再贅述（不熟悉的伙伴可以參閱前面的題解）。

????????在一般的BFS流程中，用visited只需要記錄已訪問(wèn)過(guò)的節(jié)點(diǎn)，而無(wú)需記錄其對(duì)應(yīng)的距離。本題解在最后統(tǒng)一進(jìn)行距離求和，所以必須將每個(gè)節(jié)點(diǎn)的距離記錄下來(lái)，最自然的做法當(dāng)然是在visited中將節(jié)點(diǎn)和距離信息一起記錄下來(lái)，因此在本題解中用dict()實(shí)現(xiàn)visited（一般只記憶節(jié)點(diǎn)的話用set()即可）。

3. 代碼及測(cè)試

# -*- 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))

????????運(yùn)行結(jié)果：N = 7, count=22212, tCost = ?0.073(sec)