Last Updated: 2024-03-18 14:22:36 Monday
-- TOC --
所谓Block Voting System，即不同的voter手中的票有一个权重，即blocks。比如有A，B，C三个voter，它们的blocks分别是3，2，1，不管A是投赞成for，还是反对against，都是3份，权重比较高。当这3个人voting时，有下面两种情况会出现tied，即赞成和反对的票数相等：
每个voter背后，可能是一个一致行动的小组，voter不管如何投出他的票，都是代表整个小组投票，票数就是小组人数。
问题：当我们知道一个voting block list时，计算一共有多少种tied的情况？
== 下面的内容存档，它们都只是在遍历所有的组合，而不是Dynamic Programming...!!! ==
先来个recursive算法压压惊：
def num_ties(blocks, for_v=0, against_v=0):
if not blocks:
if for_v == against_v:
return 1
return 0
i = num_ties(blocks[1:], for_v+blocks[0], against_v)
j = num_ties(blocks[1:], for_v, against_v+blocks[0])
return i+j
assert num_ties((1,2,3)) == 2
assert num_ties((1,1,2,3,5)) == 4
assert num_ties((4,5,6,7,8,9)) == 0
assert num_ties((10,15,9,4,4,8,12,8)) == 10
下面尝试用DP自底向上循环的方式计算：
def num_ties_loop(blocks):
if not blocks:
return 0
r = [-blocks[0], blocks[0]]
for i in blocks[1:]:
sr = []
for v in r:
sr.append(v+i)
sr.append(v-i)
r = sr
return r.count(0)
assert num_ties_loop((1,2,3)) == 2
assert num_ties_loop((1,1,2,3,5)) == 4
assert num_ties_loop((4,5,6,7,8,9)) == 0
assert num_ties_loop((10,15,9,4,4,8,12,8)) == 10
for i in range(10,24):
blocks = [j for j in range(i)]
assert num_ties(blocks) == num_ties_loop(blocks)
这个问题更进一步，计算每一种具体的投票可能，依然先上recursive版本：
def enum_votes(blocks):
if not blocks:
return [((),())]
x = [((f+(blocks[0],),a)) for f,a in enum_votes(blocks[1:])]
y = [((f,a+(blocks[0],))) for f,a in enum_votes(blocks[1:])]
return x+y
print('block list: (1,)')
for f,a in enum_votes((1,)):
print(f,a)
print('block list: (1,2)')
for f,a in enum_votes((1,2)):
print(f,a)
print('block list: (1,2,3)')
for f,a in enum_votes((1,2,3)):
print(f,a)
储存结构的设计很关键，list内嵌tuple，tuple内嵌套tuple，表示两种投票方向的不同。
输出：
block list: (1,)
(1,) ()
() (1,)
block list: (1,2)
(2, 1) ()
(1,) (2,)
(2,) (1,)
() (2, 1)
block list: (1,2,3)
(3, 2, 1) ()
(2, 1) (3,)
(3, 1) (2,)
(1,) (3, 2)
(3, 2) (1,)
(2,) (3, 1)
(3,) (2, 1)
() (3, 2, 1)
下面尝试DP版本：
def enum_votes_loop(blocks):
if not blocks:
return []
r = [((blocks[0],),()),
((),(blocks[0],))]
for i in blocks[1:]:
sr1 = [(f+(i,),a) for f,a in r]
sr2 = [(f,a+(i,)) for f,a in r]
r = sr1 + sr2
return r
print('[dp] block list: (1,)')
for f,a in enum_votes_loop((1,)):
print(f,a)
print('[dp] block list: (1,2)')
for f,a in enum_votes_loop((1,2)):
print(f,a)
print('[dp] block list: (1,2,3)')
for f,a in enum_votes_loop((1,2,3)):
print(f,a)
for i in range(10,20):
blocks = [j for j in range(i)]
assert len(enum_votes(blocks)) == len(enum_votes_loop(blocks))
输出相同，只是顺序不同而已：
[dp] block list: (1,)
(1,) ()
() (1,)
[dp] block list: (1,2)
(1, 2) ()
(2,) (1,)
(1,) (2,)
() (1, 2)
[dp] block list: (1,2,3)
(1, 2, 3) ()
(2, 3) (1,)
(1, 3) (2,)
(3,) (1, 2)
(1, 2) (3,)
(2,) (1, 3)
(1,) (2, 3)
() (1, 2, 3)
这个问题还可以更进一步，计算每一个block其决定作用的次数，即这个block的票数直接决定投票结果，或者打平。这个计算，需要利用enum_votes_loop的结果，但其本身与DP无关，略！
本文链接：https://cs.pynote.net/ag/dp/202307242/
-- EOF --
-- MORE --