pinter-8.A.2 permutation to disjoint cycles.md

8.A.2 - A Book of Abstract Algebra by Charles C. Pinter

using System;
using System.Collections.Generic;
using System.Linq;

using static System.Console;

namespace pinter_8.A._1_multiplying_permutations
{
    class Program
    {
        static void display(Dictionary<int, int> f)
        {
            foreach (var key in f.Keys.OrderBy(elt => elt)) Write($"{key} "); WriteLine();
            foreach (var key in f.Keys.OrderBy(elt => elt)) Write($"{f[key]} "); WriteLine();
        }

        static void display(List<List<int>> cycles)
        {
            foreach (var cycle in cycles)
            {
                Write("(");
                foreach (var i in cycle) Write(i);
                Write(")");
            }

            WriteLine();
        }
        
        static Dictionary<int, int> permutation(string s) =>
            Enumerable.Range(1, s.Count())
            .Zip(
                s.Select(elt => elt - '0'),
                (k, v) => (key: k, value: v))
            .ToDictionary(kv => kv.key, kv => kv.value);

        static List<int> get_cycle(Dictionary<int,int> f, int i)
        {
            var result = new List<int>();
            
            while(true)
            {
                if (result.Contains(i)) return result;

                result.Add(i);

                i = f[i];
            }
        }
        
        static List<List<int>> permutation_to_disjoint_cycles(Dictionary<int, int> f) =>
            Enumerable.Range(1, f.Keys.Max())
            .Aggregate(
                new List<List<int>>(),
                (result, i) => 
                    result.SelectMany(elt => elt).Contains(i) ? result : 
                    f[i] == i                                 ? result : 
                    result.Concat(new List<List<int>> { get_cycle(f, i) }).ToList());
        
        static void display_permutation_as_disjoint_cycles(string s)
        {
            display(permutation(s)); WriteLine();

            display(permutation_to_disjoint_cycles(permutation(s)));

            WriteLine("--------------------");
        }

        static void Main(string[] args)
        {
            display_permutation_as_disjoint_cycles("492517683");
            display_permutation_as_disjoint_cycles("749238165");
            display_permutation_as_disjoint_cycles("795312486");
            display_permutation_as_disjoint_cycles("987436512");
        }
    }
}