/**
 * Author: Kacper Blachut
 * Purpose: Applies Burnside's Lemma, Polya's Enumaration or Color Enumeration on chosen group actions
 *
 * Program used in "O pewnym problemie przeliczania unikalnych przeksztalcen na zbiorach skonczonych" for Malopolski Konkurs Prac Matematycznych 2022.
 * Doesn't have a UI
 */

using System;
using System.Collections.Generic;
using System.Text;

namespace RotatingHypercubes
{
    class GeneralCase
    {
        public class Cycle
        {
            public IntPL Elements;

            public Cycle(IntPL newElements)
            {
                Elements = newElements;
            }

            public int Length()
            {
                return Elements.Count;
            }
            public override string ToString()
            {
                return Elements.ToString();
            }
        }
        public class Permutation
        {
            ///An object representing a permutation

            //The permutation
            public int[] Pi;

            public Permutation(int[] NewPi)
            {
                if (IsPiCorrect(NewPi))
                {
                    Pi = NewPi;
                }
                else
                {
                    Pi = NewPi;
                    Console.Write("\nPermutation is incorrect: \n" + this);

                    //Throw exception:
                    Pi[0] = Pi[NewPi.Length];
                }
            }

            //Checks if all the numbers in the permutation are within the range <0, length>
            public bool IsPiCorrect(int[] NewPi)
            {
                bool[] Temp = new bool[NewPi.Length];

                for (int i = 0; i < NewPi.Length; i++)
                {
                    if (NewPi[i] <= NewPi.Length && NewPi[i] >= 1)
                    {
                        if (!Temp[NewPi[i] - 1])
                        {
                            Temp[NewPi[i] - 1] = true;
                        }
                        else
                        {
                            return false;
                        }
                    }
                    else
                    {
                        return false;
                    }
                }

                return true;
            }
            //Gets the lengths of all cycles inside the permutation
            public int[] GetCycleLengths()
            {
                IntPL CycleLengths = new IntPL();
                bool[] IndexesChecked = new bool[Pi.Length];

                for (int CurrentIndex = 1; CurrentIndex <= Pi.Length; CurrentIndex++)
                {
                    //Checks if the current index has already been in a previous cycle
                    if (!IndexesChecked[CurrentIndex - 1])
                    {
                        int RunningIndex = CurrentIndex;
                        int RunningLength = 1;

                        //Console.Write(RunningIndex);

                        //Follows the cycle
                        while (Pi[RunningIndex - 1] != CurrentIndex)
                        {
                            IndexesChecked[RunningIndex - 1] = true;
                            RunningIndex = Pi[RunningIndex - 1];
                            RunningLength++;

                            //Console.Write(", " + RunningIndex);
                        }
                        IndexesChecked[RunningIndex - 1] = true;

                        //Console.Write(" - " + RunningLength);
                        //Console.WriteLine();

                        CycleLengths.Add(RunningLength);
                    }

                    IndexesChecked[CurrentIndex - 1] = true;
                }

                return CycleLengths.ToArray();
            }
            //Converts the permutation into an array of cycles
            public Cycle[] ConvertToCycles()
            {
                List<Cycle> Cycles = new List<Cycle>();
                bool[] IndexesChecked = new bool[Pi.Length];

                for (int CurrentIndex = 1; CurrentIndex <= Pi.Length; CurrentIndex++)
                {
                    //Checks if the current index has already been in a previous cycle
                    if (!IndexesChecked[CurrentIndex - 1])
                    {
                        int RunningIndex = CurrentIndex;
                        IntPL RunningCycle = new IntPL();
                        RunningCycle.Add(RunningIndex);

                        //Console.Write(RunningIndex);

                        //Follows the cycle
                        while (Pi[RunningIndex - 1] != CurrentIndex)
                        {
                            IndexesChecked[RunningIndex - 1] = true;
                            RunningIndex = Pi[RunningIndex - 1];
                            RunningCycle.Add(RunningIndex);

                            //Console.Write(", " + RunningIndex);
                        }
                        IndexesChecked[RunningIndex - 1] = true;

                        //Console.Write(" - " + RunningLength);
                        //Console.WriteLine();

                        Cycles.Add(new Cycle(RunningCycle));
                    }

                    IndexesChecked[CurrentIndex - 1] = true;
                }

                return Cycles.ToArray();
            }

            public override string ToString()
            {
                return ArrayToString(Pi);
            }
        }
        public class IntPL : List<int>
        {
            public override string ToString()
            {
                return "(" + String.Join(", ", this) + ")";
            }
        }

        public class PermGroup
        {
            ///An object representing a permutation group
            ///Does not check for validity in permutations

            //The set of permutations
            public Permutation[] Symmetries;

            public PermGroup(Permutation[] newSymmetries)
            {
                if(IsPermutationLengthEqual(newSymmetries))
                {
                    Symmetries = newSymmetries;
                }
                else
                {
                    Symmetries = newSymmetries;
                    Console.Write("\nPermutation lengths in this PermutationGroup are not equal: \n" + this);

                    //Throw exception:
                    Symmetries[0] = Symmetries[newSymmetries.Length];
                }
            }

            //Checks if all the permutation lengths are equal
            public bool IsPermutationLengthEqual(Permutation[] newSymmetries)
            {
                if(newSymmetries.Length != 0)
                {
                    int FirstLength = newSymmetries[0].Pi.Length;

                    for(int i = 0; i < newSymmetries.Length; i++)
                    {
                        if(newSymmetries[i].Pi.Length != FirstLength)
                        {
                            return false;
                        }
                    }

                    return true;
                }
                else
                {
                    return true;
                }
            }
            public override string ToString()
            {
                return ArrayToString(Symmetries);
            }
        }
        public class CLSGroup
        {
            ///Cycle Length Short-notation Group
            ///An object representing a group as a set of lengths of cycles in the symmetries on some set
            ///Can't do operations on symmetries
            ///But is really helpful in formulas like: Burnside's Lemma or Polya's Enumaration Theorem

            //The possible cycle lengths that a permutation can have in this group
            public IntPL[] CycleLengths;
            //The x-th number is the amount of permutations that have cycle lengths equal to the x-th term in CycleLengths
            public int[] NumOfPermsOfType;

            public CLSGroup(IntPL[] newCycleLengths, int[] newNumOfPermsOfType)
            {
                if(IsPermutationLengthEqual(newCycleLengths))
                {
                    CycleLengths = newCycleLengths;

                    if(IsNumOfPermsCorrect(newCycleLengths, newNumOfPermsOfType))
                    {
                        NumOfPermsOfType = newNumOfPermsOfType;
                    }
                    else
                    {
                        NumOfPermsOfType = newNumOfPermsOfType;
                        Console.WriteLine("The number of permutations that has certain cycle lengths is wrongly defined: \n" + this);

                        //Throw exception
                        NumOfPermsOfType[0] = NumOfPermsOfType[NumOfPermsOfType.Length];
                    }
                }
                else
                {
                    CycleLengths = newCycleLengths;
                    Console.WriteLine("The lengths of permutation in this CLSGroup are not equal: \n" + this);

                    //Throw exception
                    CycleLengths[0] = CycleLengths[CycleLengths.Length];
                }
            }

            //Checks if the sum of cycle lengths in each permutation is equal
            public bool IsPermutationLengthEqual(IntPL[] newCycleLengths)
            {
                if(newCycleLengths.Length != 0)
                {
                    int FirstPermutationLength = 0;
                    foreach(int CycleLength in newCycleLengths[0])
                    {
                        FirstPermutationLength += CycleLength;
                    }

                    for(int i = 0; i < newCycleLengths.Length; i++)
                    {
                        int RunningLength = 0;
                        foreach(int CycleLength in newCycleLengths[i])
                        {
                            RunningLength += CycleLength;
                        }

                        if(RunningLength != FirstPermutationLength)
                        {
                            return false;
                        }
                    }

                    return true;
                }
                else
                {
                    return true;
                }
            }
            //Checks if the lengths of newCycleLengths and newNumOfPermsOfType are equal and if all the elements of newNumOfPermsOfType are greater than 0
            public bool IsNumOfPermsCorrect(IntPL[] newCycleLengths, int[] newNumOfPermsOfType)
            {
                if (newNumOfPermsOfType.Length == newCycleLengths.Length)
                {
                    for(int i = 0; i < newNumOfPermsOfType.Length; i++)
                    {
                        if(newNumOfPermsOfType[i] <= 0)
                        {
                            return false;
                        }
                    }
                    return true;
                }
                else
                {
                    return false;
                }
            }
            //Counts the number of symmetries in the group
            public int NumOfSymmetries()
            {
                int Total = 0;

                for(int i = 0; i < NumOfPermsOfType.Length; i++)
                {
                    Total += NumOfPermsOfType[i];
                }

                return Total;
            }
            //Calculates the size of the set the group is acting on
            public int GetSetSize()
            {
                if(CycleLengths.Length > 0 && CycleLengths[0].Count > 0)
                {
                    int LengthOfPermutation = 0;

                    foreach(int CycleLength in CycleLengths[0])
                    {
                        LengthOfPermutation += CycleLength;
                    }

                    return LengthOfPermutation;
                }

                return 0;
            }

            public override string ToString()
            {
                return ArrayToString(CycleLengths) + "\n" + ArrayToString(NumOfPermsOfType);
            }
        }

        static public void PrintArray(Array array)
        {
            Console.Write("{");
            for(int i = 0; i < array.Length - 1; i++)
            {
                Console.Write(array.GetValue(i) + "; ");
            }
            Console.Write(array.GetValue(array.Length - 1) + "}");
        }
        static public string ArrayToString(Array array)
        {
            string Output = "(";
            for (int i = 0; i < array.Length - 1; i++)
            {
                Output = Output.Insert(Output.Length, array.GetValue(i) + ", ");
            }
            Output =  Output.Insert(Output.Length, array.GetValue(array.Length - 1) + ")");

            return Output;
        }


        public static int BurnsidesLemma(CLSGroup Group, int NumOfColors)
        {
            int Total = 0;

            for(int i = 0; i < Group.NumOfPermsOfType.Length; i++)
            {
                Total += Group.NumOfPermsOfType[i] * (int) MathF.Pow(NumOfColors, Group.CycleLengths[i].Count);
            }

            Total /= Group.NumOfSymmetries();

            return Total;
        }
        public static int BurnsidesLemma(PermGroup Group, int NumOfColors)
        {
            int Total = 0;

            for(int i = 0; i < Group.Symmetries.Length; i++)
            {
                Total += (int) MathF.Pow(NumOfColors, Group.Symmetries[i].ConvertToCycles().Length);
            }

            Total /= Group.Symmetries.Length;

            return Total;
        }
        public static int PolyaEnumaration(CLSGroup Group, int[] ColorWeights)
        {
            int Total = 0;

            for(int SymmetryIndex = 0; SymmetryIndex < Group.CycleLengths.Length; SymmetryIndex++)
            {
                int SymmetrySubTotal = Group.NumOfPermsOfType[SymmetryIndex];

                for(int CycleIndex = 0; CycleIndex < Group.CycleLengths[SymmetryIndex].Count; CycleIndex++)
                {
                    int CycleSubTotal = 0;

                    for(int ColorIndex = 0; ColorIndex < ColorWeights.Length; ColorIndex++)
                    {
                        CycleSubTotal += (int)MathF.Pow(ColorWeights[ColorIndex], Group.CycleLengths[SymmetryIndex].ToArray()[CycleIndex]);
                    }

                    SymmetrySubTotal *= CycleSubTotal;
                }

                Total += SymmetrySubTotal;
            }

            Total /= Group.NumOfSymmetries();

            return Total;
        }
        public static int ColorEnumaration(CLSGroup SetGroup, CLSGroup ColorGroup)
        {
            long Total = 0;

            for(int ColorSymmetryIndex = 0; ColorSymmetryIndex < ColorGroup.CycleLengths.Length; ColorSymmetryIndex++)
            {
                int SetSymmetrySubTotal = 0;

                int[] TempColorSymmetryCycleLengths = ColorGroup.CycleLengths[ColorSymmetryIndex].ToArray();

                for(int SetSymmetryIndex = 0; SetSymmetryIndex < SetGroup.CycleLengths.Length; SetSymmetryIndex++)
                {
                    int SetCycleSubTotal = 1;

                    int[] TempSetSymmetryCycleLengths = SetGroup.CycleLengths[SetSymmetryIndex].ToArray();

                    for(int SetCycleIndex = 0; SetCycleIndex < TempSetSymmetryCycleLengths.Length; SetCycleIndex++)
                    {
                        int ColorCycleSubTotal = 0;

                        for(int ColorCycleIndex = 0; ColorCycleIndex < TempColorSymmetryCycleLengths.Length; ColorCycleIndex++)
                        {
                            if(TempSetSymmetryCycleLengths[SetCycleIndex] % TempColorSymmetryCycleLengths[ColorCycleIndex] == 0)
                            {
                                ColorCycleSubTotal += TempColorSymmetryCycleLengths[ColorCycleIndex];
                            }
                        }

                        SetCycleSubTotal *= ColorCycleSubTotal;
                    }

                    SetSymmetrySubTotal += SetCycleSubTotal * SetGroup.NumOfPermsOfType[SetSymmetryIndex];
                }

                Total += SetSymmetrySubTotal * ColorGroup.NumOfPermsOfType[ColorSymmetryIndex];
            }

            Total /= SetGroup.NumOfSymmetries() * ColorGroup.NumOfSymmetries();

            return (int) Total;
        }

        public class CLSBasics
        {
            //Cycle groups - vertices of an n-gon - rotational symmetry
            public CLSGroup C3 = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1, 1 },
                new IntPL { 3 } }, new int[] { 1, 2 });
            public CLSGroup C4 = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1, 1, 1 },
                new IntPL { 2, 2 },
                new IntPL { 4 } }, new int[] { 1, 1, 2 });

            //Dihedral groups - vertices of an n-gon - rotational and mirror symmetry
            public CLSGroup D4 = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1, 1, 1 },
                new IntPL { 2, 1, 1 },
                new IntPL { 2, 2 },
                new IntPL { 4 } }, new int[] { 1, 2, 3, 2 });

            //Symmetric groups - disjoint set of points - all symmetries
            public CLSGroup S2 = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1 },
                new IntPL { 2 } }, new int[] { 1, 1 });
            public CLSGroup S3 = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1, 1 },
                new IntPL { 1, 2},
                new IntPL { 3 } }, new int[] { 1, 3, 2 });
            public CLSGroup S4 = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1, 1, 1 },
                new IntPL { 2, 1, 1 },
                new IntPL { 2, 2 },
                new IntPL { 3, 1 },
                new IntPL { 4 } }, new int[] { 1, 6, 3, 8, 6 });
            public CLSGroup S8 = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1, 1, 1, 1, 1, 1, 1 },
                new IntPL { 2, 1, 1, 1, 1, 1, 1 },
                new IntPL { 2, 2, 1, 1, 1, 1 },
                new IntPL { 2, 2, 2, 1, 1 },
                new IntPL { 2, 2, 2, 2 },
                new IntPL { 3, 1, 1, 1, 1, 1 },
                new IntPL { 3, 2, 1, 1, 1 },
                new IntPL { 3, 2, 2, 1 },
                new IntPL { 3, 3, 1, 1 },
                new IntPL { 3, 3, 2 },
                new IntPL { 4, 1, 1, 1, 1 },
                new IntPL { 4, 2, 1, 1 },
                new IntPL { 4, 2, 2 },
                new IntPL { 4, 3, 1 },
                new IntPL { 4, 4 },
                new IntPL { 5, 1, 1, 1 },
                new IntPL { 5, 2, 1 },
                new IntPL { 5, 3 },
                new IntPL { 6, 1, 1 },
                new IntPL { 6, 2 },
                new IntPL { 7, 1 },
                new IntPL { 8 } }, new int[] { 1, 28, 210, 420, 105, 112, 1120, 1680, 1120, 1120, 420, 2520, 1260, 3360, 1260, 1344, 4032, 2688, 3360, 3360, 5760, 5040 });

            //Octahedral symmetry - vertices of a cube - rotational and mirror symmetry
            public CLSGroup O = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1, 1, 1, 1, 1, 1, 1 },
                new IntPL { 2, 2, 1, 1, 1, 1 },
                new IntPL { 2, 2, 2, 2 },
                new IntPL { 3, 3, 1, 1 },
                new IntPL { 4, 4 },
                new IntPL { 6, 2 } }, new int[] { 1, 6, 13, 8, 12, 8 });
            //Klein four-group - vertices of a rectangle - rotational and mirror symmetry
            public CLSGroup V = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1, 1, 1 },
                new IntPL { 2, 2 } }, new int[] { 1, 3 });
            //Quaternion group - vertices of a cube - custom symmetry
            public CLSGroup Q = new CLSGroup(new IntPL[] {
                new IntPL { 1, 1, 1, 1, 1, 1, 1, 1 },
                new IntPL { 2, 2, 2, 2 },
                new IntPL { 4, 4 } }, new int[] { 1, 1, 6 });


            public CLSGroup Multiply(CLSGroup Group, int Multiple)
            {
                IntPL[] newCycleLengths = new IntPL[Group.CycleLengths.Length];

                for(int SymmetryIndex = 0; SymmetryIndex < Group.CycleLengths.Length; SymmetryIndex++)
                {
                    int[] TempCycles = Group.CycleLengths[SymmetryIndex].ToArray();
                    newCycleLengths[SymmetryIndex] = new IntPL();

                    for(int CycleIndex = 0; CycleIndex < Group.CycleLengths[SymmetryIndex].Count; CycleIndex++)
                    {
                        for(int M = 0; M < Multiple; M++)
                        {
                            newCycleLengths[SymmetryIndex].Add(TempCycles[CycleIndex]);
                        }
                    }
                }

                return new CLSGroup(newCycleLengths, Group.NumOfPermsOfType);
            }
        }
        public class PermBasics
        {
            public PermGroup C4 = new PermGroup(new Permutation[] {
                new Permutation(new int[] {1, 2, 3, 4}),
                new Permutation(new int[] {4, 1, 2, 3}),
                new Permutation(new int[] {3, 4, 1, 2}),
                new Permutation(new int[] {2, 3, 4, 1}) });
        }

        static void Main(string[] args)
        {
            CLSBasics TC = new CLSBasics();
            PermBasics TP = new PermBasics();
            //Console.WriteLine(BurnsidesLemma(TP.C4, 10));
            Console.WriteLine(ColorEnumaration(TC.O, TC.S8));
        }
    }
}