最小生成集问题


起源

七段数码管是这样的东西:
七段数码管

当我们想要显示一位数字的时候，实际就是去点亮七段LED中的某几段，比如数字1就是bc，2就是abged，以此类推……

为了方便写单片机程序，我们需要做个编码(补上一个不使用的比特h):

1
2
3
4
5
6
7
8
9
10
11
12
DIG | a b c d e f g h | HEX
----|-----------------|------
'0' | 1 1 1 1 1 1 0 0 | 0xFC
'1' | 0 1 1 0 0 0 0 0 | 0x60
'2' | 1 1 0 1 1 0 1 0 | 0xDA
'3' | 1 1 1 1 0 0 1 0 | 0xF2
'4' | 0 1 1 0 0 1 1 0 | 0x66
'5' | 1 0 1 1 0 1 1 0 | 0xB6
'6' | 1 0 1 1 1 1 1 0 | 0xBE
'7' | 1 1 1 0 0 0 0 0 | 0xE0
'8' | 1 1 1 1 1 1 1 0 | 0xFE
'9' | 1 1 1 1 0 1 1 0 | 0xF6

如此之后我们可以发现，其实并不用对每个需要显示的图案都去逐位列举以计算编码，如果我们知道’2’和’5’的编码，我们就可以直接通过按位或运算得到’8’的编码，ie. 0xDA | 0xB6 == 0xFE

于是现在的问题就是，我们最少选择几个、选择哪几个基本编码，就可以通过常用的位运算得到其他的编码，下面进一步抽象并给出这个问题的数学描述

描述

给定数字0~9的二进制表示集合N，给定算子集合OP = { NOT, OR, AND, XOR }，求N在OP下的最小生成集

一般化扩展: 给定一个二进制数的集合N = {N1, N2, ..., Nn}，给定一个N上算子的集合OP = {OP1, OP2, ..., OPk}，求N在OP下的最小生成集

解

目前没有想到合理的多项式时间算法，暂时先放个暴力解:

MGS_bf.pyview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#!/usr/bin/env python3
# Author: Armit
# Create Time: 2019/10/05 

# minimal generator set - brute force

import time
import numpy as np

NUMBERS = np.array([ # '0' ~ '9'
  0x3F, 0x06, 0x5B, 0x4F, 0x66, 
  0x6D, 0x7D, 0x07, 0x7F, 0x6F,
], dtype=np.uint8)
NOT = lambda x, y: ~x
AND = lambda x, y: x & y
OR  = lambda x, y: x | y
XOR = lambda x, y: x ^ y
OPS = [ NOT, AND, OR, XOR ]

to_bin = lambda x, w=8: bin(x)[2:].rjust(w, '0')

def timer(fn):
  def wrapper(*args, **kwargs):
    s = time.time()
    ret = fn(*args, **kwargs)
    t = time.time()
    print('[Timer] %.4fs' % (t - s))
    return ret
  return wrapper

@timer
def MGS_bf(N=NUMBERS, OP=OPS):
  target, solutions = set(N), [ ]
  nlen = len(N)
  for sel in range(2**nlen):
    sel_bin = to_bin(sel, nlen)
    partial = { N[i] for i in range(len(sel_bin)) if sel_bin[i] == '1' }
    partial_orig = partial.copy() # save orig for ans
    
    size = 0
    while size != len(partial): # search result extended
      size = len(partial)
      new_partial = { op(x, y) for op in OP for x in partial for y in partial }
      partial.update(new_partial)
      
      if partial.issuperset(target):
        solutions.append(partial_orig)
        break

  print('>> %d solutions found in total' % len(solutions))
  groups = { }
  for sol in solutions:
    sz = len(sol)
    if sz in groups: groups[sz].append(sol)
    else: groups[sz] = [ sol ]

  min_sols = groups.get(sorted(groups)[0])  # just need the shortest groups
  return [sorted([np.where(NUMBERS == g)[0][0] for g in sol]) for sol in min_sols]
  
if __name__ == '__main__':
  print('over {OR, AND, XOR, NOT}')
  for sol in MGS_bf():
    print(sol)
  print()

  print('over {OR, AND}')
  for sol in MGS_bf(NUMBERS, [OR, AND]):
    print(sol)
  print()
  
  print('over {OR, NOT}')
  for sol in MGS_bf(NUMBERS, [OR, NOT]):
    print(sol)
  print()
    
  print('over {AND, NOT}')
  for sol in MGS_bf(NUMBERS, [AND, NOT]):
    print(sol)
  print()