from itertools import permutations as Perm
from math import factorial as mF
import numpy as np
import pandas as pd
import string
import time
def getScore(team):
"""
Givent a list of team members, determine the score.
Parameters:
team - List of team members, denoted by their index.
Returns:
score - Maximal increasing subsequencing.
"""
n = len(team)
#Subsequence creation.
seq = [1] * n
#Start with the second place in the line.
for i in range(1, n):
#For everyone in the line before them, check who prefers a lesser temperature.
for prev in range(0, i):
#If they do...
if team[i] > team[prev]:
#Their subsequence rank is the maximum of either their current rank
#or 1 more than the rank of the team member recently compared to.
seq[i] = max(seq[i], seq[prev] + 1)
# Return the score
score = max(seq)
return(score)
old_s = 0
N = []
SI = []
Numerator = []
EV = []
Time = []
for n in range(1, 12) :
start = time.time()
scores = []
for team in list(Perm(range(n))) :
scores.append(getScore(team))
#print(scores)
s = sum(scores)
N.append(n)
SI.append(s - old_s * n)
Numerator.append(s)
EV.append(s / mF(n))
Time.append(round(time.time()-start, 4))
old_s = s
data = {'Team Size': N,
'Total Subsequence Increases': SI,
'Numerator': Numerator,
'Average Score' : EV,
'Run Time' : Time}
print(pd.DataFrame(data))
Team Size Total Subsequence Increases Numerator Average Score Run Time 0 1 1 1 1.000000 0.0000 1 2 1 3 1.500000 0.0000 2 3 3 12 2.000000 0.0000 3 4 10 58 2.416667 0.0000 4 5 45 335 2.791667 0.0000 5 6 251 2261 3.140278 0.0038 6 7 1638 17465 3.465278 0.0270 7 8 12300 152020 3.770337 0.2522 8 9 104877 1473057 4.059350 2.7334 9 10 1000135 15730705 4.334961 32.5711 10 11 10534062 183571817 4.598861 430.6407