2005.sagews

class Coalitions:
    "use binary counting to generate all possible coalitions"
    def __init__(self, participants):
        self.participants = participants # maximale binäre Stellen
        self.bin_v = [] # Vektor Länge max mit Zweierpotenzen
        self.bin = 1
        self.bin_v.append(self.bin)
        
        for x in range(self.participants ):
            self.bin = self.bin*2
            self.bin_v.append(self.bin)
        
    def get_coalition(self, x):
        "returns binary value of x as list"
        self.coalition = []
        for i in range(1, self.participants +1):
            if x - self.bin_v[self.participants -i] >= 0:
                x = x-self.bin_v[self.participants -i]
                self.coalition.append(1)
            else:
                self.coalition.append(0)
        return self.coalition

# Example: alle vierstelligen Binaerzahlen als Liste ausgeben: 
#coal = Coalitions(4) 
#for i in range(2^4):
#    print coal.get_coalition(i)

def w_sum(v,w):
    "v: binary List, w: weights"
    "returns weighted sum, v[i] decides if w[i] is counted"
    if len(v) != len(w):
        print "len(v) != len(w) FAIL"
        return 0
        
    sum = 0
    for i in range(len(v)):
        if v[i] == 1:
            sum = sum + w[i]
    return sum        

def abs_banzhaf_index(w, q, j):
    if j >= len(w):
        print "j >= len(w) FAIL"
        return 0
        
    coal = Coalitions(len(w))
    count = 0
    for i in range(2^len(w)):
        c = coal.get_coalition(i)
        if c[j] == 1:
            pass # this coalition includes member j, so just skip
        else:
            if w_sum(c, w) < q:
                c[j] = 1
                if w_sum(c, w) >= q:
                    count += 1
                    #print c
    return count

w = [10,5,4]
q = 10

for j in range(len(w)):
    abs_banzhaf_index(w,q,j)

4 0 0

w = [9,6,4]
q = 10

for j in range(len(w)):
    abs_banzhaf_index(w,q,j)

2 2 2

w = [4,4,4,2,2,1]
q = 12

for j in range(len(w)):
    abs_banzhaf_index(w,q,j)

10 10 10 6 6 0

w = [10,10,10,10,5,5,3,3,2]
q = 41

for j in range(len(w)):
    abs_banzhaf_index(w,q,j)

53 53 53 53 29 29 21 21 5