#computes character table of S_n, for small enough n
#note: correct up to n = 25

import math
#parameters
print_representatives = True

#computes conjugacy number of conjugacy classes and cycle type
def f(n):
  big_list = []
  if n != 1:
    returned = f(n-1)
    for l in returned:
      temp = l
      temp.append(1)
      big_list.append(temp)
    if n/2 >= 2:
      first_num = 2
      while first_num <= n-2:
        returned = f(first_num) #we have fresh list of f(j)
        for l in returned:
          if l.count(1) == 0:
            diff = 2
            pretotal = 0
            for p in l:
              pretotal = pretotal + p
            while diff + pretotal < n:
              diff = diff + 1
            if diff <= l[len(l) - 1]:
              l.append(diff)
              big_list.append(l)
        
        first_num = first_num+1
  big_list.append([n])
  return big_list

def Order(cycle_partition,n):
  centralizer_size = 1
  i = 1
  while i <= n:
    k = cycle_partition.count(i)
    if k != 0:
      centralizer_size = centralizer_size * (i**k) * math.factorial(k)
    i = i + 1
  return int(round(math.factorial(n) / centralizer_size))
def GetConjugacyClasses(n):
  conjugacy_classes = []
  for l in f(n):
    temp = (l, Order(l,n))
    conjugacy_classes.append(temp)
    
  return(conjugacy_classes)
#interface loop thingy
end = False
x = 0
while end == False:
	tmp = input("Compute the characer table of S_n, for n =")
	if tmp == "end":
		end = True
	else:
		x = int(tmp)
		if x <= 0:
		  print("please enter n > 0") #?
		else:
		  bloop = GetConjugacyClasses(x)
		  print("The group S_n has %3u conjugacy classes." %len(bloop))
		  if print_representatives:
		    print("The representative for each class are lsited below:")
		    for m in bloop:
		      print("   ",m) #I lied, I still need to finish this properly