from math import factorial as F
import matplotlib
from matplotlib.animation import FuncAnimation as FA
from matplotlib.ticker import StrMethodFormatter as SMF
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns

#Create a list of N! lists, each a different permutation of the N cars ordered by speed.
def orders(cars):
    if len(cars) == 1:
        return [cars]
    else :
        next_car = cars[0]
        cars = cars[1:]
        orders_so_far = []
        for order in orders(cars) :
            for insert in range(len(order)+1) :
                orders_so_far.append(order[:insert] + [next_car] + order[insert:])

    return(orders_so_far)



#Given an order of N cars as a list, it splits them up into Lane 1 and 2, and groups them by speed.
#Returns the number of groups.
def procession(order) :
    df = pd.DataFrame({"Preferred_Speed": order,
                       "Actual_Speed": np.nan,
                       "Lane": np.nan})
    
    #First car travels at its speed and stays in first lane.
    df.iat[0, 1] = df.iat[0,0]
    df.iat[0, 2] = 1
    
    #The remaining N-1 cars...
    for car in range(1, len(order)):
        ps = df.iat[car, 0]
        
        #Look at actual speed of last car in Lane 1.
        lane_1_speed = (df[(df.Lane == 1)]["Actual_Speed"].tolist())[-1]
        
        #If car preferred speed is less, stay in Lane 1.
        if ps < lane_1_speed :
            df.iat[car, 1] = df.iat[car, 0]
            df.iat[car, 2] = 1
        
        #Look at actual speed of last car in Lane 2.
        else:
            lane_2_speeds = df[(df.Lane == 2)]["Actual_Speed"].tolist()
            #It could be empty...
            if lane_2_speeds == []:
                lane_2_speed = ps
            else:
                lane_2_speed = lane_2_speeds[-1]
                
            #If Lane 2 < Lane 1, stay in Lane 1.
            if lane_2_speed < lane_1_speed :
                df.iat[car, 1] = lane_1_speed
                df.iat[car, 2] = 1
            
            #Else, move to Lane 2.
            else :
                df.iat[car, 2] = 2
                #If preferred speed is greater than last car of Lane 2, slow down.
                if ps > lane_2_speed :
                    df.iat[car, 1] = lane_2_speed
                #Else, travel at preferred speed.    
                else :    
                    df.iat[car, 1] = df.iat[car, 0]
    
    unique_groups = len(set(df.Actual_Speed))
    return(unique_groups)


def gen_all_groups(N):
    
    cars = list(range(1, N+1)) 
        
    groups = []    
    for order in orders(cars):
        proc = procession(order)
        groups.append(proc)
    return(groups)

values = []

for i in range(2,11):
    values.append(gen_all_groups(i))
    print(i)

2
3
4
5
6
7
8
9
10

def processionDist() :

    #Plot Setup.
    matplotlib.rc_file_defaults()
    fig = plt.figure(figsize = (10, 7))
    ax = fig.add_subplot(111)

    #Footnote font size.
    font = {'size' : 14}

    def animate(i):
        plt.cla()
        ax.set_title("Distribution of Car Groups", fontsize = 22)
        ax.set_xlabel("Number of Groups", fontsize = 18)
        ax.set_ylabel("Frequency", fontsize = 18)
        ax.yaxis.set_major_formatter(SMF('{x:,.0f}'))
        ax.tick_params(axis = 'both', labelsize = 16)

        bins = list(range(1, i+4))
        hist = ax.hist(values[i],
                       bins = bins,
                       align = "left",
                       color = "#22A884") 
        ax.set_xticks(ticks = bins)
        
        if i ==0 :
            ax.set_yticks(ticks = [0,1,2])
        
        
        avg_val = sum(values[i])/F(i+2)
        ax.axvline(x = avg_val, color = "#481567")

        #Update footnote text.
        ax.annotate("Number of Cars: %.0f" % (i+2),
                    xy = (0.15, 0.12),
                    xytext = (0.15, 0.12),
                    xycoords = 'figure fraction',
                    textcoords = 'figure fraction',
                    fontsize = 16,
                    color = '#481567')
        ax.annotate("Average Number",
                    xy = (0.70, 0.17),
                    xytext = (0.70, 0.17),
                    xycoords = 'figure fraction',
                    textcoords = 'figure fraction',
                    fontsize = 16,
                    color = '#481567')
        ax.annotate("of Groups: %.4f" % avg_val,
                    xy = (0.70, 0.12),
                    xytext = (0.70, 0.12),
                    xycoords = 'figure fraction',
                    textcoords = 'figure fraction',
                    fontsize = 16,
                    color = '#481567')
        return hist
    
    
    
    #Run animation.
    anim = FA(fig, init_func = None, func = animate, frames = 9, interval = 3000, blit = False)       

    
    
    #Save animation.
    anim.save('2022.08.26 Express.mp4');
    
processionDist()

for v in values:
    print(sum(v))

4
17
84
485
3236
24609
210572
2004749
21033900

Rohan Lewis

2022.08.29