import numpy as np
import pandas as pd
import random
from itertools import combinations
from sklearn.externals import joblib
from tqdm import tqdm_notebook
from matplotlib import pyplot as plt
import numba as nb

class VCG_Auction_Process(object):
    def __init__(self,value_mat_origin):
        self.value_mat_origin=value_mat_origin
        self.value_mat=self.value_mat_origin
        self.allocation=self.value_mat.columns # For single-item condition
        self.best_price=0 #Initialization
    @nb.jit
    def who_win(self):
        '''
        Pick up the winners for each item, if bids are the same, then a winner will be randomly picked
        '''
        self.winner_list=[] #Bidder index for each winner of the item
        self.second_price_list=[]
        winner_temp=[]
        for item_set in self.allocation:
            item_represent=item_set[0] #Because all other items in the set share the same value
            winner_temp.append(np.where(self.value_mat[item_represent]==np.max(self.value_mat[item_represent]))[0])
        for item_set_index,winner in enumerate(winner_temp):
            item_set=self.allocation[item_set_index] # The item set like [0,1]
            item_represent=item_set[0]# Representation
            if len(winner)>1:
                #print("Item set {:} has multiple winner: {:}".format(item_set,winner))
                random.seed(10)
                self.winner_list.append(random.choice(winner))
                second_price=sorted(self.value_mat[item_represent])[-2]
                # Add the payment of each winner, pay your value if the "same" occur
                self.second_price_list.append(second_price) 
            else:
                self.winner_list.append(winner[0])
                second_price=sorted(self.value_mat[item_represent])[-2]
                self.second_price_list.append(second_price)
        #print(self.value_mat)
        #print(self.winner_list)
        return self.winner_list,self.second_price_list
    
    def winner_price(self):
        '''
        Calculate the price that the winner does to other agents and the mechanism will charge the price for each winner
        
        Make sure function who_win is run in advance
        '''
        self.welfare_list=[] # List for the welfare contributed by the winner. the sum of this list is the social welfare
        self.price_list=[] # List for the price that the winner charged, for losers they don't pay
        value_winner_list=[]
        value_without_winner_list=[]
        # Get the value list of winner
        # With the winners
        for item_set_index,winner in enumerate(self.winner_list):
            item_set=self.allocation[item_set_index] # The item set like [0,1]
            item_represent=item_set[0]# Representation
            value_winner_list.append(self.value_mat[item_represent].iloc[winner])
        self.welfare_list=value_winner_list
        # Without the winners
        value_without_winner_list=self.second_price_list
        # Contribution of the winner
        
        ctrib_list=list(map(lambda x: x[0]-x[1],zip(value_winner_list,value_without_winner_list)))
        # Price of the winner charged by the mechanism
        self.price_list=list(map(lambda x: x[0]-x[1],zip(value_winner_list,ctrib_list)))
        return self.price_list,self.welfare_list
    def allocate_items(self,allocation):
        '''
        Allocate different sets of items
        '''
        self.allocation=allocation# Consider a finxed allocation case
        self.update_value_mat()
    @nb.jit
    def update_value_mat(self):
        '''
        Update the value of bidders for item sets as the value of item sets are the maximum value inside
        '''
        self.value_mat=self.value_mat_origin.copy()
        for set_index,item_set in enumerate(self.allocation):
            for bidder,value in self.value_mat.iterrows():
                self.value_mat.iloc[bidder][item_set]=np.max(self.value_mat.iloc[bidder][item_set])
                
    def find_best_allocation_price(self,current_price):
        if current_price>=self.best_price:
            self.best_allocation=self.allocation # Initialization
            self.best_price=current_price
        
    def begin(self,possible_allocations):
        f=open('allocation_price.txt','w+')
        for allocation in tqdm_notebook(possible_allocations): #Define your possible_allocations here:
            self.allocate_items(allocation)
            self.who_win()
            self.winner_price()
            self.find_best_allocation_price(np.sum(np.sum(self.price_list)))
            f.write('For Allocation: {:} Pirce charged by mechanism {:} and total {:}\n'.format(
            self.allocation,self.price_list,np.sum(self.price_list)))
        f.close()
        print('Best allocation: {:} and the mechanism charges {:}'.format(self.best_allocation,self.best_price))

# variables
value_mat_origin=pd.read_table('Assignment#2-Q8-values.txt',delimiter=' ',header=None,sep='\\t')
value_mat_origin=value_mat_origin.drop([8],axis=1)
value_mat_origin

columns=value_mat_origin.columns
columns=list(columns)
possible_allocations_8=[]
possible_allocations_7=[]
possible_allocations_6=[]
possible_allocations_5=[]
possible_allocations_4=[]
possible_allocations_3=[]
possible_allocations_2=[]
possible_allocations_1=[]

def divide(item,l):
    ll=l.copy()
    ll.remove(item)
    return ll
def merge_unit(two_item,l):
    '''
    Just deal with two items
    '''
    if len(two_item)>2:
        print('Emission of merge_unit')
    else:
        return [   [ [two_item[0]],[two_item[1]],l],[[two_item[0],two_item[1]],l]]
    
def add_allocation(unit_two,allocations):
    allocations.append(unit_two[0])
    allocations.append(unit_two[1])
    
def merge_three(three_items,l,allocations):
    # only one item in each set
    head1=[[e] for e in three_items]+[l]
    allocations.append(head1)
    # two item in each set
    for the_left in three_items:
        l2=divide(the_left,three_items)
        head2=[[the_left],l2]+[l]
        allocations.append(head2)
    # Three item in each set
    head3=[three_items,l]
    allocations.append(head3)
    
def merge_four(four_items,l,allocations):
    # only one item in each set
    head1=[[e] for e in four_items]+[l]
    allocations.append(head1)
    # two items in each set
    for two_item_set in combinations(four_items,2):
        two_item_set=list(two_item_set)
        left_item_set=list(set(four_items)-set(two_item_set))
        merge_three((left_item_set+two_item_set),l,allocations)
    # three items in each set
    for the_left in four_items:
        l3=divide(the_left,four_items)
        head3=[[the_left],l3]+[l]
        allocations.append(head3)
    # Four item in each set
    head4=[four_items,l]
    allocations.append(head4)

def merge_five(five_items,l,allocations):
    # only one item in each set
    head1=[[e] for e in five_items]+[l]
    allocations.append(head1)
    # two items in each set
    for two_item_set in combinations(five_items,2):
        two_item_set=list(two_item_set)
        left_item_set=five_items.copy()
        for i in range(len(two_item_set)):
            left_item_set.remove(two_item_set[i])
        merge_four((left_item_set+two_item_set),l,allocations)
    # three items in each set (at most)
    for three_item_set in combinations(five_items,3):
        three_item_set=list(three_item_set)
        left_item_set=five_items.copy()
        for i in range(len(three_item_set)):
            left_item_set.remove(three_item_set[i])
        merge_three((left_item_set+three_item_set),l,allocations)
        
def merge_six(six_items,l,allocations):
    # only one item in each set
    head1=[[e] for e in six_items]+[l]
    allocations.append(head1)
    # two items in the maximum set(at moist)
    for two_item_set in combinations(six_items,2):
        two_item_set=list(two_item_set)
        left_item_set=six_items.copy()
        for i in range(len(two_item_set)):
            left_item_set.remove(two_item_set[i])
        # Left set is all 1-item set
        head2=[[e] for e in left_item_set]+[two_item_set]+[l]
        allocations.append(head2)
        # Left set has 1 two-item set
        for left_two_item_set in combinations(left_item_set,2):
            left_two_item_set=list(left_two_item_set)
            left_left_item_set=left_item_set.copy()
            for j in range(2):
                left_left_item_set.remove(left_two_item_set[j])
                head3=[[e] for e in left_left_item_set]+[left_two_item_set]+[two_item_set]+[l]
                allocations.append(head3)
            # All the six-items divied into three two-item sets
            head4=[left_left_item_set]+[left_two_item_set]+[two_item_set]+[l]
            allocations.append(head4)

# 8 item sets
possible_allocations_8=[[[0,1,2,3,4,5,6,7]]]
joblib.dump(possible_allocations_8,'possible_allocations_8.asv')
print(len(possible_allocations_8))

# 7 item sets
for item in columns:
    possible_allocations_7.append([[item],divide(item,columns)])
joblib.dump(possible_allocations_7,'possible_allocations_7.asv')
print(len(possible_allocations_7))

# 6 item sets
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        unit=merge_unit([item,item2],l2)
        add_allocation(unit,possible_allocations_6)
joblib.dump(possible_allocations_6,'possible_allocations_6.asv')
print(len(possible_allocations_6))

# 5 item sets        
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        for item3 in l2:
            l3=divide(item3,l2)
            merge_three([item,item2,item3],l3,possible_allocations_5)
joblib.dump(possible_allocations_5,'possible_allocations_5.asv')
print(len(possible_allocations_5))

# 4 item sets
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        for item3 in l2:
            l3=divide(item3,l2)
            for item4 in l3:
                l4=divide(item4,l3)
                merge_four([item,item2,item3,item4],l4,possible_allocations_4)
joblib.dump(possible_allocations_4,'possible_allocations_4.asv')
print(len(possible_allocations_4))

# 3 item sets
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        for item3 in l2:
            l3=divide(item3,l2)
            for item4 in l3:
                l4=divide(item4,l3)
                for item5 in l4:
                    l5=divide(item5,l4)
                    merge_five([item,item2,item3,item4,item5],l5,possible_allocations_3)
joblib.dump(possible_allocations_3,'possible_allocations_3.asv')
print(len(possible_allocations_3))

# 2 item sets
for item in columns:
    l1=divide(item,columns)
    for item2 in l1:
        l2=divide(item2,l1)
        for item3 in l2:
            l3=divide(item3,l2)
            for item4 in l3:
                l4=divide(item4,l3)
                for item5 in l4:
                    l5=divide(item5,l4)
                    for item6 in l5:
                        l6=divide(item6,l5)
                        merge_six([item,item2,item3,item4,item5,item6],l6,possible_allocations_2)
joblib.dump(possible_allocations_2,'possible_allocations_2.asv')
print(len(possible_allocations_2))

# 1 item sets
possible_allocations_1.append([[e] for e in columns])
possible_allocations_1=possible_allocations_1[0]
# Dump data
joblib.dump(possible_allocations_1,'possible_allocations_1.asv')
print(len(possible_allocations_1))

vcg=VCG_Auction_Process(value_mat_origin)
vcg.begin(possible_allocations_6)