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

RdouTyping 发布于2021-09-24 09:48 / 815人阅读

摘要：汉明距离可以用异或操作实现。这个问题其实可以看作是，具有个节点的全连接无向图，每条边的权重值代表两个节点所代表的数字的段码显示的二进制表示之间的汉明距离。

1. 问题描述

2. 解题分析

3. 代码及测试

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 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全解

GPU云服务器云服务器最短路算法的程序最复杂的程序算法最厉害的算法想法程序 webrtc 1.62.0.7

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/120960.html

程序员的算法趣题Q48: 翻转得到交错排列

摘要：由此可得初始状态为终止状态黑白或交错有两种，分别是翻转运算在圆圈上翻转连续张牌，可以用一个比特的有个比特为的整数称为掩码与表示排列状态的整数进行按比特异或运算得到。求余部分代表没有移出比特部分的值。目录 1. 问题描述 2. 解题分析 2.1 圆圈排列的表示 2.2 翻转运算 2.3 ...

lvzishen 2021-10-09 09:44 评论0 收藏0
程序员的算法趣题Q49: 欲速则不达

摘要：本文先考虑深度优先搜索。深度优先搜索算法流程如下最后，将初始化为，初始化，和分别初始化为适当的全零数组，然后调用到最终退出后所得到的即为所求结果。目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 2. 解题分析本题是要找最长路径，应该...

BlackMass 2021-10-11 10:58 评论0 收藏0
程序员的算法趣题Q51: 同时结束的沙漏

摘要：结合上下文猜测应该是说沙子同时漏完的意思。问题的焦点在于如何表示不同的排列状态以及如何处理沙漏翻转。上一篇完美洗牌完美洗牌下一篇糖果恶作剧本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解目录 1. 问题描述 1.1 原题的表述 2. 解题分析 2.1 转换为线...

bovenson 2021-10-12 10:12 评论0 收藏0
程序员的算法趣题Q19: 朋友的朋友还是朋友吗？

摘要：基于以上讨论可得，本题求解流程如下所示代码及测试运行结果上一篇水果酥饼日下一篇异或杨辉三角形本系列总目录参见程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述六度空间理论非常有名。大概的意思是1个人只需要通过6个中间人就...

oogh 2021-09-10 10:51 评论0 收藏0