資訊專欄INFORMATION COLUMN
摘要：漢明距離可以用異或操作實現。這個問題其實可以看作是，具有個節點的全連接無向圖，每條邊的權重值代表兩個節點所代表的數字的段碼顯示的二進制表示之間的漢明距離。
目錄
????????問題：求把10個數字全部顯示出來時，亮燈/滅燈的切換次數最少的顯示順序，以及這個切換次數。
????????注：原題從答案來看是不包括第一個數字顯示時從全黑到顯示該數字所需要的亮滅切換次數的。不過這個不影響解題，但是可能會影響答案。
????????從暴力搜索（原書中使用“全量搜索”這個詞很貼切）著手。
????????10個數字的不同排列順序共有10!=factorial(10)=3628800種，針對每一種排列順序進行切換次數的統計即可。
????????本題解中用numpy array存儲各數字顯示所需要的燈亮滅表示矩陣，每行表示一個數字，表示使用7段碼對應的二進制表示。
????????切換次數的計算可以理解為兩個二進制序列之間的漢明距離(hamming distance)，即兩個二進制序列之間的不同的數的個數。漢明距離可以用異或操作實現。
????????此外，各數字的二進制表示之間的漢明距離總共只有10*10=100個（連自己與自己之間的距離也算上，雖然不用。考慮到查找實現的便利，(k,j)和(j,k)也分開來算，雖然它們是相等的）可以預先計算好，這樣可以避免在遍歷搜索時的大量的重復計算。
# -*- coding: utf-8 -*-"""Created on Wed Sep 22 07:37:19 2021@author: chenxy"""import sysimport timeimport datetimeimport mathimport randomfrom typing import List# from queue import Queuefrom collections import dequeimport itertools as itfrom math import sqrt, floor, ceilimport numpy as npclass Solution: segs = np.array([[1,1,1,1,1,1,0], [0,1,1,0,0,0,0], [1,1,0,1,1,0,1], [1,1,1,1,0,0,1], [0,1,1,0,0,1,1], [1,0,1,1,0,1,1], [1,0,1,1,1,1,1], [1,1,1,0,0,0,0], [1,1,1,1,1,1,1], [1,1,1,1,0,1,1]]) distArray = dict() minDistSum = np.sum(segs) minOrder = None def initDistArray(self): for i in range(len(self.segs)): for j in range(len(self.segs)): self.distArray[tuple([i,j])] = np.sum(self.segs[i] ^ self.segs[j]) def printDistArray(self): print(self.distArray) def minToggle(self): for order in it.permutations(list(range(10))): # print(order) distSum = 0 #np.sum(self.segs[0]) for k in range(9): distSum += self.distArray[(order[k],order[k+1])] if self.minDistSum > distSum: self.minDistSum = distSum self.minOrder = order return self.minDistSum, self.minOrder if __name__ == "__main__": sln = Solution() sln.initDistArray() # sln.printDistArray() t1 = time.perf_counter() minDistSum, minOrder = sln.minToggle() tCost = time.perf_counter() - t1 print("Number of toggles = {0}, order = {1}, tCost = {2}".format(minDistSum, minOrder,tCost)) 運行結果：
Number of toggles = 13, order = (0, 8, 6, 5, 9, 4, 1, 7, 3, 2), tCost = ?8.640sec
4. 后記
????????運行時間有點長，需要考慮進一步優化。
????????這個問題其實可以看作是，具有10個節點的全連接無向圖，每條邊的權重值代表兩個節點所代表的數字的7段碼顯示的二進制表示之間的漢明距離。因此本題就轉化為就該圖中任意一條最長無重復路徑的權重總和。這其實就是著名（惡名昭彰）的旅行商問題。這是一個NP問題，但是只有10個節點還可以對付。接下來考慮用遞歸+Memoization的方法來試一試會不會變得更快一些。
? ? ? ? 上一篇：Q36: 翻轉骰子
? ? ? ? 下一篇：
????????本系列總目錄參見：程序員的算法趣題：詳細分析和Python全解
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/120960.html
摘要：由此可得初始狀態為終止狀態黑白或交錯有兩種，分別是翻轉運算在圓圈上翻轉連續張牌，可以用一個比特的有個比特為的整數稱為掩碼與表示排列狀態的整數進行按比特異或運算得到。求余部分代表沒有移出比特部分的值。 目錄 1. 問題描述 2. 解題分析 2.1 圓圈排列的表示 2.2 翻轉運算 ?2.3 ...
摘要：本文先考慮深度優先搜索。深度優先搜索算法流程如下最后，將初始化為，初始化，和分別初始化為適當的全零數組，然后調用到最終退出后所得到的即為所求結果。 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 1. 問題描述 2. 解題分析 ????????本題是要找最長路徑，應該...
摘要：結合上下文猜測應該是說沙子同時漏完的意思。問題的焦點在于如何表示不同的排列狀態以及如何處理沙漏翻轉。上一篇完美洗牌完美洗牌下一篇糖果惡作劇本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 1.1 原題的表述 2. 解題分析 2.1 轉換為線...
摘要：基于以上討論可得，本題求解流程如下所示代碼及測試運行結果上一篇水果酥餅日下一篇異或楊輝三角形本系列總目錄參見程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問題描述 ????????六度空間理論非常有名。大概的意思是1個人只需要通過6個中間人就...
閱讀 3274·2023-04-25 18:03
閱讀 1143·2021-11-15 11:38
閱讀 5521·2021-10-25 09:45
閱讀 840·2021-09-24 09:48
閱讀 2271·2021-09-22 15:34
閱讀 1734·2019-08-30 15:44
閱讀 2674·2019-08-30 13:12
閱讀 603·2019-08-29 16:05
