#We simulate the parallel Greedy algorithm
import random
import math

#The principal variables are defined here
max_load = 3
n = 1000000
#Balls[i]=j means that the ball i is in the bin j (if j is -1 then i hasn't commited)
Balls = range(n)
#Bins[i] is the load of the bin i
Bins = range(n)
#Bins_round[i] is the list of the balls that have sent a message to bin i during the round simulated
bins_round = range(n)
#Balls_round[i] is the list of bins that have received a message from i during the round simulated
balls_round = range(n)
#An useful list
l = range(n)


#It puts k in all the cases of the list l
def place(k,l):
        for i in range(len(l)):
                l[i] = k

#It allows to begin a new simulation
def remise_zero():              
        place(-1,Balls)
        place(0,Bins)

#It begins a simulation by defining the different lists according to the number of balls
def change_n(k):
        global n
        global Balls
        global Bins
        global bins_round
        global balls_round
        global l
        n = k
        l = range(n)
        Balls = range(n)
        Bins = range(n)
        bins_round = range(n)
        balls_round = range(n)
        l = range(n)
                

#This function simulates a round of the basic greedy algorithm with ranks
#nb_balls is the number of balls left
#Current_ball lists the balls that are still here : we have nb_balls = len(current_balls)
#nb_c is the number of messages sent per round
def round(nb_balls,current_balls,nb_c):
        global max_load
        #For this round, the choices hasn't been made so far
        place([],balls_round)
        place([],bins_round)
        for i in range(nb_balls):
                #Each ball i chooses nb_c bins among n to send a message to
                balls_round[current_balls[i]] = random.sample(l,nb_c)
                #We add the ball current_ball[i] to the bins_round[b]
                for b in balls_round[current_balls[i]]:
                        bins_round[b] = bins_round[b] + [current_balls[i]]
        #For each bin we shuffle the messages received
        for i in range(n):
                random.shuffle(bins_round[i])
        for i in range(n):
                if len(balls_round[i]) !=  0:
                #For each ball who hasn't been placed so far we find the best rated message it has sent
                        min_h = n
                        choice_commit = 0
                        for b in balls_round[i]:
                                if (bins_round[b]).index(i) < min_h:
                                        min_h = (bins_round[b]).index(i)
                                        choice_commit = b
                        #If it can commit into the bin which received this message, it does
                        if Bins[choice_commit] < max_load:
                                Balls[i] = choice_commit
                                Bins[choice_commit] = Bins[choice_commit] + 1
        
#It sumulates one time the algorithm    
def simulation():
        global max_load
        current_balls = range(n)
        remise_zero()
        nb_balls = n
        nb_rounds = 0
        #Here we choose the first parameter : the number of messages during the first round
        nb_c = 5
        #Here is the second : the max_load during the first round
        max_load = 2
        while nb_rounds < 1:
                round(nb_balls,current_balls,nb_c)
                #Current_balls are the non-commited balls
                current_balls = [b for b in range(n) if Balls[b] == -1]
                nb_balls = len(current_balls)
                nb_rounds = nb_rounds +1
                #Parameters for the second round
                if nb_rounds == 1:
                        max_load = 3
                        nb_c = 5
                #Parameter for the third round
                if nb_rounds == 2:
                        max_load = 3
                        nb_c = 5
                print(nb_balls)
        return(nb_balls)


#Allow to repeat simulations and get an average number of what returns simulations
#Simulation can easily be changed to return the number of bins with a certain load, the number of remaining balls after 1,2 or 3 rounds
def nb_moy(essais):
        max_load_moy = 0.
        for i in range(essais):
                remise_zero()
                max_load_moy = max_load_moy + (float(simulation()))/(float(essais))     
        print(max_load_moy)


nb_moy(10)