源代码
from itertools import chain,combinations as comb if __name__ == '__main__': L = list('abcdefg') C = [[''.join(c) for c in list(comb(L,i+1)) if 'g' in c] for i in range(7)] D = list(chain.from_iterable(C)) X = [e for e in D if 'a' in e and 'b' not in e and 'f' not in e or 'd' in e and 'c' not in e and 'e' not in e] E = [d for d in D if d not in X] L = list('abcdef')*2 A = [L[i:j] for i in range(len(L)) for j in range(i+1,len(L)+1) if len(L[i:j])<7] B = list(set([''.join(sorted(a)) for a in A])) F = sorted(B + E) print('可表达字符总数：',len(F)) print('所有组合的列表：',F)
运行结果
可表达字符总数： 80
所有组合的列表： ['a', 'ab', 'abc', 'abcd', 'abcde', 'abcdef', 'abcdefg', 'abcdeg', 'abcdf', 'abcdfg', 'abcdg', 'abcef', 'abcefg', 'abceg', 'abcf', 'abcfg', 'abcg', 'abdef', 'abdefg', 'abdeg', 'abef', 'abefg', 'abeg', 'abf', 'abfg', 'abg', 'acdef', 'acdefg', 'acdfg', 'acefg', 'acfg', 'adef', 'adefg', 'aef', 'aefg', 'af', 'afg', 'b', 'bc', 'bcd', 'bcde', 'bcdef', 'bcdefg', 'bcdeg', 'bcdfg', 'bcdg', 'bcefg', 'bceg', 'bcfg', 'bcg', 'bdefg', 'bdeg', 'befg', 'beg', 'bfg', 'bg', 'c', 'cd', 'cde', 'cdef', 'cdefg', 'cdeg', 'cdfg', 'cdg', 'cefg', 'ceg', 'cfg', 'cg', 'd', 'de', 'def', 'defg', 'deg', 'e', 'ef', 'efg', 'eg', 'f', 'fg', 'g']
解题思路
分两类进行分别计算：第一类是g段处于点亮状态，即在'abcdefg'中取出所有字母组合，但要排除不包含g的，排除后有64种；最后还要排除含a但不含b或f的、含d但不含c或e的共15个（“有了a但没有b或f就形成ag不连通”，另一个同理），排除后共49种组合。
第二类是g段不点亮状态即不包含g段，可以看作a~f组成的是一个环（零），所以需要在双倍长度的字符串'abcdefabcdef'中取出所有长度为1~6的所有子串，共有57种；每个字串内部作排序后再去重，留下31种组合。这样，两类总共合计有80种组合。
import itertools class UnionFindSet(): def __init__(self,n): self.count = 0 # 当前连通分量数目 # self.count = n # 不连通区域 self.father=[x for x in range(n)] def find(self,x): root = x while self.father[root]!=root: # 找根节点 root=self.father[root] # 路径压缩 while x != root: o = self.father[x] # 找x的父节点 self.father[x] = root # 把x的父节点设置成刚才找到的根 x = o # 往上一层 return root def union(self,x,y): x,y=self.find(x),self.find(y) if x != y: self.father[y]=x # 合并 self.count +=1 return 0 result = 0 nums = [x for x in range(7)] for x in range(1,8): # 每次用的晶体管个数 for k in itertools.combinations(nums, x): #从所有的晶体管中按个数要求不重复的拿。 l = len(k)#晶体管的个数 ufs = UnionFindSet(l) #两两的逐个选取 for a in range(l): for b in range(a+1,l): #根据下图的数字判断两个晶体管是否相邻。 if abs(k[a]-k[b])==1 or (k[a]==1 and k[b]==6) or (k[a]==2 and k[b]==6) or (k[a]==4 and k[b]==6) or (k[a]==0 and k[b]==5): ufs.union(a,b) if l-ufs.count==1: #比如当用到三个二极管的时候只需要链接两次，那么当晶体管个数减去链接次数为1的时候符合要求。 result += 1 print(result)
