@@ -0,0 +1,2745 @@
+import random%0Afrom bisect import bisect%0Aimport math%0Aimport copy%0A%0Anum_participants = 6%0Anum_to_eliminate = 3%0Anum_cakes = 30%0Acake_knowledge_set = xrange(5,16)%0Anum_trials = 50000%0Azip_pow = 0.5%0Adebug = False%0A%0A#generate zipfian distribution for cake probability%0Acake_prob = %7B%7D%0Afor i in xrange(num_cakes):%0A    cake_prob%5Bi%5D = float(1.0)/math.pow(i+1,zip_pow)%0A%0A#functions%0Adef weighted_choice(choices):%0A    values = choices.keys()%0A    weights = choices.values()%0A    total = 0%0A    cum_weights = %5B%5D%0A    for w in weights:%0A        total += w%0A        cum_weights.append(total)%0A    x = random.random() * total%0A    i = bisect(cum_weights, x)%0A    return values%5Bi%5D%0A%0Adef gen_person_cake(ck):%0A    person_cake = %5B%5D%0A    for i in xrange(num_participants):%0A        participant_cake_prob = copy.copy(cake_prob)%0A        cake_list = set(%5B%5D)%0A        for j in xrange(ck):%0A            selected = weighted_choice(participant_cake_prob)%0A            cake_list.add(selected)%0A            del participant_cake_prob%5Bselected%5D%0A        person_cake.append(cake_list)%0A    return person_cake%0A%0A#main%0Afor cake_knowledge in cake_knowledge_set:%0A    print %22cake_knowledge =%22, cake_knowledge%0A    fail = %5B0%5D*num_participants%0A    for nt in xrange(num_trials):%0A        #if nt %25 1000  == 0:%0A            #print %22trial%22, nt, %22%5Cr%22%0A        person_cake = %5B%5D%0A        #give everyone knowledge of random selection of cakes%0A        #for np in xrange(num_participants):%0A        #    person_cake.append(set(random.sample(xrange(30), cake_knowledge)))%0A        person_cake = gen_person_cake(cake_knowledge)%0A        if debug:%0A            print person_cake%0A%0A        cake_remaining = set(xrange(30))%0A        participant_id = 0%0A        participant_remaining = set(xrange(num_participants))%0A        while True:%0A            participant_id = participant_id %25 num_participants%0A            if participant_id in participant_remaining:%0A                overlap = person_cake%5Bparticipant_id%5D & cake_remaining%0A                if debug:%0A                    print %22%5Cnparticipant =%22, participant_id%0A                    print %22%5Ctremainining cake =%22, cake_remaining%0A                    print %22%5Ctcake overlap =%22, overlap%0A                if len(overlap) == 0:%0A                    fail%5Bparticipant_id%5D += 1%0A                    if debug:%0A                        print %22%5Ct****FAILED****%22, fail%0A                    participant_remaining.remove(participant_id)%0A                    if (num_participants - len(participant_remaining)) == num_to_eliminate:%0A                        break%0A                else:%0A                    cake_remaining.remove(random.choice(list(overlap)))%0A                %0A            participant_id += 1%0A%0A    fail = %5B (%22%7B0:.3f%7D%22.format(float(item)/(num_trials))) for item in fail%5D%0A    print fail%0A%0A        %0A        %0A

Create compute_pos_prob.py