程序员的算法趣题Q37: 翻转7段码

1. 问题描述

问题：求把10个数字全部显示出来时，亮灯/灭灯的切换次数最少的显示顺序，以及这个切换次数。

注：原题从答案来看是不包括第一个数字显示时从全黑到显示该数字所需要的亮灭切换次数的。不过这个不影响解题，但是可能会影响答案。

2. 解题分析

从暴力搜索（原书中使用“全量搜索”这个词很贴切）着手。

10个数字的不同排列顺序共有10!=factorial(10)=3628800种，针对每一种排列顺序进行切换次数的统计即可。

本题解中用numpy array存储各数字显示所需要的灯亮灭表示矩阵，每行表示一个数字，表示使用7段码对应的二进制表示。

切换次数的计算可以理解为两个二进制序列之间的汉明距离(hamming distance)，即两个二进制序列之间的不同的数的个数。汉明距离可以用异或操作实现。

此外，各数字的二进制表示之间的汉明距离总共只有10*10=100个（连自己与自己之间的距离也算上，虽然不用。考虑到查找实现的便利，(k,j)和(j,k)也分开来算，虽然它们是相等的）可以预先计算好，这样可以避免在遍历搜索时的大量的重复计算。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Wed Sep 22 07:37:19 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
from   math import sqrt, floor, ceil
import numpy as np


class 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的方法来试一试会不会变得更快一些。