Block Voting System,集体投票系统

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