DampOverdueAlligatorgar

#Computes Character Table of S_n, for small enough n.
#note:

#import
import math

#parameters
print_representatives = True
print_table = True


#----------------# Conjugacy Classes of S_n #----------------#

#Finds list of conjugacy classes of S_n. Note: n > 1.
def f(classes_list, n): 
  classes_n = []
  #print("classes_list")
  #print(classes_list)
  for representative in (classes_list[(n-1)-1]):
    #print("representative in classes_list[(n-1)-1]")
    #print(representative)
    temp = list(representative[0])
    temp.append(1)
    classes_n.append(temp)
  if n/2 >= 2:
    for first_degree in range(2, n-1):
      for representative in classes_list[(first_degree)-1]:
        if representative[0].count(1) == 0:
          diff = 2
          total = 0
          for p in representative[0]:
            total += p
          while diff + total < n:
            diff += 1
          if diff <= representative[0][len(representative[0])-1]:
            temp = list(representative[0])
            temp.append(diff)
            classes_n.append(temp)
  classes_n.append([n])
  return classes_n

#Computes the order of a conjugacy class in S_n
def Order(representative, n):
  if representative.count(1) == n:
    return 1
  centralizer_size = 1
  for i in range(1,n+1):
    k = representative.count(i)
    centralizer_size *= ((i)**k) * math.factorial(k)
  return int(round(math.factorial(n) / centralizer_size))

#Computes conjugacy classes of S_m for 1 <= m <= n
def GetConjugacyClasses(biglist_classes, n):
  if biglist_classes[1] < n:
    for m in range(biglist_classes[1], n):
      biglist_classes[0].append([])
      if m+1 == 1:
        biglist_classes[0][m].append(([1], 1))
        #print("biglist_classes[0][m]")
        #print(biglist_classes[0][m])
      else:
        for rep in f(biglist_classes[0], m+1):
          class_tuple = (rep, Order(rep,m+1))
          biglist_classes[0][m].append(class_tuple)
    biglist_classes = (biglist_classes[0], len(biglist_classes[0]))
   
  return biglist_classes

#------------------------------------------------------------#



#-----------------# Character Table of S_n  #-----------------#

#----# Standard Characters #----------------------------------#

def TrivialCharacter(ConjugacyClassesS_n):
  x_1 = []
  for i in range(len(ConjugacyClassesS_n)):
    x_1.append(1)
  return(x_1, "x_1", "Trivial")

def SignCharacter(ConjugacyClassesS_n):
  x_2 = []
  for g_rep in ConjugacyClassesS_n:
    sign = 1
    for e in g_rep[0]:
      if e % 2 == 0:
        sign *= -1
    x_2.append(sign)
  return(x_2, "x_2", "Sign")

def RegularCharacter(ConjugacyClassesS_n):
  pi_reg = []
  for g_rep in ConjugacyClassesS_n:
    pi_reg.append(g_rep[0].count(1))
  return(pi_reg, "pi_reg", "Regular")

def StandardCharacter(pi_reg):
  x_3 = []
  for g_char in pi_reg[0]:
    x_3.append(g_char - 1)
  return(x_3, "x_3", "pi_reg - x_1")

#----# Character Arithmetic & Operations #-------------------#

def CharacterTensor(x_1, x_2, ConjugacyClassesS_n, k):
  x_new = []
  for i in range(len(ConjugacyClassesS_n)):
    x_new.append(x_1[0][i] * x_2[0][i])

  return(x_new, "x_%u" %k, x_1[1] + "*" + x_2[1])

def InnerProduct(x_1, x_2, ConjugacyClassesS_n):
  summation = 0
  group_order = 0
  for g_i in range(len(ConjugacyClassesS_n)):
    temp = (complex(x_1[0][g_i]).conjugate() * complex(x_2[0][g_i]))
    summation += temp * ConjugacyClassesS_n[g_i][1]
  for rep in ConjugacyClassesS_n:
    group_order += rep[1]
  return (summation / group_order)

#------------------------------------------------------------#


#------------------------# "main()"? #-----------------------#

end = False
x = 0
while end == False:
  bl_classes = ([],0)
  bl_chars = []
  x = int(input("Compute the character table of S_n, for n ="))
  if x <= 0:
    print("Please enter n > 0. Quitting.")
    end = True
  else:
    #Compute conjugacy classes of S_m for 1 <= m <=n
    bl_classes = GetConjugacyClasses(bl_classes, x)
    print("The group S_%2u has %5u conjugacy classes." %(x, len(bl_classes[0][x-1])))
    if print_representatives:
      print("The representatives for each class are listed below:")
      for representative in bl_classes[0][x-1]:
        print("   ", representative) #I lied, its in list format..

    #Compute character table of S_n
    if len(bl_chars) < x:
      for i in range(len(bl_chars), x):
        bl_chars.append((([],[]), False))
    
    #Find standard characters
    if bl_chars[x-1][1] == False:
      #Get x_1 (Trivial)
      bl_chars[x-1][0][0].append(TrivialCharacter(bl_classes[0][x-1]))

      if x > 1:
        #Get x_2 (Sign)
        bl_chars[x-1][0][0].append(SignCharacter(bl_classes[0][x-1]))
      if x > 2:
        #Get pi_reg (Regular Character)
        bl_chars[x-1][0][1].append(RegularCharacter(bl_classes[0][x-1]))
        bl_chars[x-1][0][0].append(StandardCharacter(bl_chars[x-1][0][1][0]))
      if x > 3:
        #Get x_3 (Standard Character)
        temp = CharacterTensor(bl_chars[x-1][0][0][1], bl_chars[x-1][0][0][2],
          bl_classes[0][x-1], 4)

        #Check if irreducible
        return_val = InnerProduct(temp, temp, bl_classes[0][x-1])
        if round(return_val.imag) == 0 and round(return_val.real) == 1:
          bl_chars[x-1][0][0].append(temp)

        #maybe some while function here.. but
        #???? "Wat do? :V"

        if len(bl_classes[0][x-1]) - len(bl_chars[x-1][0][0]) == 1:
          #Compute the last irreducible character
          x_last = []
          char_number = len(bl_classes[0][x-1])
          summation = 0
          for i in range(len(bl_chars[x-1][0][0])):
            summation += (bl_chars[x-1][0][0][i][0][0] **2)
          temp = round(math.sqrt(math.factorial(x) - summation))
          x_last.append(temp)

          summation = 0
          for j in range(1,char_number):
            for i in range(len(bl_chars[x-1][0][0])):
              summation += bl_chars[x-1][0][0][i][0][0] * bl_chars[x-1][0][0][i][0][j]
              temp = round((summation * (-1)) / x_last[0])
            x_last.append(temp)

          #Check if irreducible
          return_val = InnerProduct((x_last,"",""), (x_last,"",""), bl_classes[0][x-1])
          if round(return_val.imag) == 0 and round(return_val.real) == 1:
            bl_chars[x-1][0][0].append((x_last, "x_%d" %char_number, "x_%d" %char_number))
    
    #Print character table of S_n
    if len(bl_chars[x-1][0][0]) - len(bl_classes[0][x-1]) == 0:
      print("The irreducible characters of S_%2u are (COMPLETE):" %(x))
    else:
      print("The irreducible characters of S_%2u are (PARTIAL):" %(x))
    for character in bl_chars[x-1][0][0]:
      print("   ", character)

#------------------------------------------------------------#



#--------------------------# NOTES #-------------------------#

# Big list of Conjugacy Classes     := ([Conjugacy Classes], k)
#             Conjugacy Classes     := [...,Conjugacy Classes S_k]
#             Conjugacy Classes S_k := ([],size)

# Big list of Character Tables      := [..., (Table S_n, True/False)]
#             Character Table  S_n  := ([..., Characters_irreducible], [..., Characters_reducible])
#             Character_m  (of S_n) := ([x_m(g_1) , ..., x_m(g_k)], "number", "description")

#------------------------------------------------------------#