# How Voting Systems Work 9, Exercise 2: Shapley-Shubik by a formula instead of listing every ordering
# For each winning coalition S in which voter i is critical, i is the pivot in |S|-1 voters before i and
# n-|S| after, so that coalition accounts for (|S|-1)! * (n-|S|)! of the n! orderings.
from math import factorial
from itertools import permutations
from time import perf_counter

def ss_formula(weights, quota):
    n = len(weights)
    score = [0] * n
    for mask in range(1 << n):
        members = [i for i in range(n) if mask >> i & 1]
        total = sum(weights[i] for i in members)
        if total >= quota:
            s = len(members)
            for i in members:
                if total - weights[i] < quota:
                    score[i] += factorial(s - 1) * factorial(n - s)
    return [x / factorial(n) for x in score]

def ss_orderings(weights, quota):
    n = len(weights)
    pivots, count = [0] * n, 0
    for order in permutations(range(n)):
        count += 1
        running = 0
        for i in order:
            running += weights[i]
            if running >= quota:
                pivots[i] += 1
                break
    return [p / count for p in pivots]

w, q = [9, 9, 7, 3, 1, 1, 4, 2], 21          # assumed: 8 voters, total 36
t0 = perf_counter(); a = ss_formula(w, q); t1 = perf_counter()
b = ss_orderings(w, q); t2 = perf_counter()
print("formula  :", [round(x, 3) for x in a])
print("orderings:", [round(x, 3) for x in b])
print("same answer:", all(abs(x - y) < 1e-12 for x, y in zip(a, b)))
big = [20, 18, 15, 12, 10, 9, 8, 7, 5, 4, 3, 2, 1, 1, 1, 1]   # 16 voters: 16! orderings is far too many to list
c = ss_formula(big, sum(big) // 2 + 1)
print("16 voters, shares sum to", round(sum(c), 6), "- largest", round(max(c), 3), "smallest", round(min(c), 3))

# Output when run:
# formula  : [0.273, 0.273, 0.215, 0.068, 0.018, 0.018, 0.096, 0.039]
# orderings: [0.273, 0.273, 0.215, 0.068, 0.018, 0.018, 0.096, 0.039]
# same answer: True
# 16 voters, shares sum to 1.0 - largest 0.184 smallest 0.008