Block Voting Systems

In voting systems such as the United States' electoral college, voters are assigned different weights which we'll refer to as voting "blocks". This makes it so that a given voter may have a greater or lesser impact on the outcome of a vote.

There are a few different ways of measuring the effectiveness of a block voting system. You'll write a couple of recursion functions to help do this.

To start, it's interesting to determine the number of ways in which a block voting system can be tied. Consider a system of 3 voting blocks: block A = 3 votes, block B = 2 votes, block C = 1 vote. The following are tie situations where each block can vote either for or against some measure:

A for vs. B + C against (3 vs. 2 + 1)

B + C for vs. A against (2 + 1 vs. 3)

With the list of voting blocks [1, 1, 2, 3, 5], on the other hand, there are a total of 4 possible tied scenarios (you should be able to enumerate them).

Complete the implementation of the function number_ties, which returns the number of tie situations arising from the provided list of voting blocks. Note that we've also include two default arguments that you may find useful in your implementation feel free to change their names and/or initial values (or add additional arguments with default values).

In [ ]:

def number_ties(blocks, for_votes=0, against_votes=0): # YOUR CODE HERE raise NotImplementedError() 

In [ ]:

from unittest import TestCase tc = TestCase() tc.assertEqual(number_ties([1, 2, 3]), 2) tc.assertEqual(number_ties([1, 1, 2, 3, 5]), 4) tc.assertEqual(number_ties([4, 5, 6, 7, 8, 9]), 0) tc.assertEqual(number_ties([10, 15, 9, 4, 4, 8, 12, 8]), 10) tc.assertEqual(number_ties([17, 10, 9, 9, 10, 10, 7, 12, 17, 13, 14, 9, 16, 16, 5]), 554) tc.assertEqual(number_ties([16, 17, 17, 30, 15, 27, 22, 20, 33, 33, 26, 22, 27, 19, 15, 16, 25, 25, 19, 18]), 8040) 

More importantly, we can compute how many situations arise in which a given block can cast the deciding vote.

E.g., given voting blocks [1, 2, 3, 4], to determine the number of times the last block casts the deciding vote, we observe that:

there are a total of eight ways in which blocks 1, 2, and 3 can vote:

1 + 2 + 3 (for) vs. 0 (against)

1 + 2 (for) vs. 3 (against)

1 + 3 (for) vs. 2 (against)

1 (for) vs. 2 + 3 (against)

2 + 3 (for) vs. 1 (against)

2 (for) vs. 1 + 3 (against)

3 (for) vs. 1 + 2 (against)

0 (for) vs. 1 + 2 + 3 (against)

in cases 2-7, the last voter (with a block of 4 votes) can cause the result to swing one way or the other (or end in a tie); we therefore say that the last block has the deciding vote in 6 cases

If you repeat the analysis for blocks 1, 2, and 3, you'll find that they are the deciding voters in 2, 4, and 4 cases, respectively (meaning that the blocks with 2 and 3 votes are equally important!).

You are to implement the function deciding_votes_per_block, which will take a list of voting blocks and return a list of times that each block is the deciding vote. You should define a separate recursive function (in the same cell) that computes the number of deciding votes given a particular block.

In [ ]:

def deciding_votes_per_block(blocks): # YOUR CODE HERE raise NotImplementedError() # YOUR CODE HERE raise NotImplementedError() 

In [ ]:

from unittest import TestCase tc = TestCase() tc.assertEqual(deciding_votes_per_block([1, 1, 2]), [2, 2, 4]) tc.assertEqual(deciding_votes_per_block([1, 2, 3, 4]), [2, 4, 4, 6]) tc.assertEqual(deciding_votes_per_block([4, 5, 6, 7, 8, 9]), [4, 8, 8, 12, 12, 16]) tc.assertEqual(deciding_votes_per_block([10, 15, 9, 4, 4, 8, 12, 8]), [40, 70, 40, 20, 20, 34, 50, 34]) tc.assertEqual(deciding_votes_per_block([17, 10, 9, 9, 10, 10, 7, 12, 17, 13, 14, 9, 16, 16, 5]), [5112, 3040, 2750, 2750, 3040, 3040, 2172, 3578, 5112, 3886, 4200, 2750, 4792, 4792, 1626])