程序員的算法趣題Q37: 翻轉(zhuǎn)7段碼(1)

RdouTyping 發(fā)布于2021-09-24 09:48 / 849人閱讀

摘要：漢明距離可以用異或操作實(shí)現(xiàn)。這個(gè)問(wèn)題其實(shí)可以看作是，具有個(gè)節(jié)點(diǎn)的全連接無(wú)向圖，每條邊的權(quán)重值代表兩個(gè)節(jié)點(diǎn)所代表的數(shù)字的段碼顯示的二進(jìn)制表示之間的漢明距離。

1. 問(wèn)題描述

2. 解題分析

3. 代碼及測(cè)試

1. 問(wèn)題描述

????????問(wèn)題：求把10個(gè)數(shù)字全部顯示出來(lái)時(shí)，亮燈/滅燈的切換次數(shù)最少的顯示順序，以及這個(gè)切換次數(shù)。

????????注：原題從答案來(lái)看是不包括第一個(gè)數(shù)字顯示時(shí)從全黑到顯示該數(shù)字所需要的亮滅切換次數(shù)的。不過(guò)這個(gè)不影響解題，但是可能會(huì)影響答案。

2. 解題分析

????????從暴力搜索（原書(shū)中使用“全量搜索”這個(gè)詞很貼切）著手。

????????10個(gè)數(shù)字的不同排列順序共有10!=factorial(10)=3628800種，針對(duì)每一種排列順序進(jìn)行切換次數(shù)的統(tǒng)計(jì)即可。

????????本題解中用numpy array存儲(chǔ)各數(shù)字顯示所需要的燈亮滅表示矩陣，每行表示一個(gè)數(shù)字，表示使用7段碼對(duì)應(yīng)的二進(jìn)制表示。

????????切換次數(shù)的計(jì)算可以理解為兩個(gè)二進(jìn)制序列之間的漢明距離(hamming distance)，即兩個(gè)二進(jìn)制序列之間的不同的數(shù)的個(gè)數(shù)。漢明距離可以用異或操作實(shí)現(xiàn)。

????????此外，各數(shù)字的二進(jìn)制表示之間的漢明距離總共只有10*10=100個(gè)（連自己與自己之間的距離也算上，雖然不用。考慮到查找實(shí)現(xiàn)的便利，(k,j)和(j,k)也分開(kāi)來(lái)算，雖然它們是相等的）可以預(yù)先計(jì)算好，這樣可以避免在遍歷搜索時(shí)的大量的重復(fù)計(jì)算。

3. 代碼及測(cè)試

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

運(yùn)行結(jié)果：

Number of toggles = 13, order = (0, 8, 6, 5, 9, 4, 1, 7, 3, 2), tCost = ?8.640sec

4. 后記

????????運(yùn)行時(shí)間有點(diǎn)長(zhǎng)，需要考慮進(jìn)一步優(yōu)化。

????????這個(gè)問(wèn)題其實(shí)可以看作是，具有10個(gè)節(jié)點(diǎn)的全連接無(wú)向圖，每條邊的權(quán)重值代表兩個(gè)節(jié)點(diǎn)所代表的數(shù)字的7段碼顯示的二進(jìn)制表示之間的漢明距離。因此本題就轉(zhuǎn)化為就該圖中任意一條最長(zhǎng)無(wú)重復(fù)路徑的權(quán)重總和。這其實(shí)就是著名（惡名昭彰）的旅行商問(wèn)題。這是一個(gè)NP問(wèn)題，但是只有10個(gè)節(jié)點(diǎn)還可以對(duì)付。接下來(lái)考慮用遞歸+Memoization的方法來(lái)試一試會(huì)不會(huì)變得更快一些。

? ? ? ? 上一篇：Q36: 翻轉(zhuǎn)骰子

? ? ? ? 下一篇：

????????本系列總目錄參見(jiàn)：程序員的算法趣題：詳細(xì)分析和Python全解