資訊專欄INFORMATION COLUMN
摘要：能以最少交換次數到達升序有序排列記為的數列記為就等價于從代表的節點在這張圖中到達對應的節點的最短路徑長度。上一篇質數矩陣質數矩陣下一篇唯一的序列本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解
目錄
????????考慮：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全解
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/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. 前言 ????????參見程序員的算法趣...
閱讀 651·2021-11-23 09:51
閱讀 3599·2021-11-15 11:38
閱讀 926·2021-10-14 09:42
閱讀 3162·2021-09-29 09:35
閱讀 2104·2021-09-03 10:33
閱讀 769·2021-07-30 16:33
閱讀 1557·2019-08-30 15:55
閱讀 1840·2019-08-30 14:04
