Permutaciones en AjGroups

Published on Author lopezLeave a comment

En mi anterior post presenté a AjGroups, una librería de clases escrita en C# que implementa conceptos y operaciones de grupos finitos. El código fuente está en mi AjCodeKata Google Project, en trunk/AjGroups.

En este post, quisiera explicar una de las implementaciones que están dentro de AjGroups: grupos basados en permutaciones.

Una permutación es una aplicación biyectiva de un conjunto S a S. Sea

S = { 0, 1, 2, 3, 4 }

Entonces, un ejemplo de permutación es:

i(0)=0, i(1)=1, i(2)=2, i(3)=3, i(4)=4

Es la permutación identidad. Otro ejemplo:

s(0)=1, s(1)=0, s(2)=2, s(3)=3, s(4)=4

Esta es un “swap”, un intercambio de los dos primeros elementos. Una permutación “rotación”:

r(0)=1, r(1)=2, r(2)=3, r(3)=4, r(4)=0

Las permutaciones pueden combinarse para dar otras permutaciones, r*s:

(r*s)(n) = r(s(n))

Las permutaciones de S son los elementos de un grupo que usa la operación *. AjGroups implementa una permutación usando la clase Element:

    public class Element : AjGroups.IElement
    {
        private byte[] values;
        public Element(params byte[] values)
        {
//....
    }

La permutación se representa en un arreglo de bytes, donde values[k] es el resultado de f(k), siendo f la permutación representada por el Element.

Element.Multiply(Element element) implementa la multiplicación:

       public Element Multiply(Element element)
        {
            int k;
            int length1 = this.values.Length;
            int length2 = element.values.Length;
            int newlength = Math.Max(length1, length2);
            byte[] newvalues = new byte[newlength];
            for (k = 0; k < newlength; k++)
            {
                if (k >= length2)
                {
                    newvalues[k] = this.values[k];
                }
                else if (element.values[k] >= length1)
                {
                    newvalues[k] = element.values[k];
                }
                else
                {
                    newvalues[k] = this.values[element.values[k]];
                }
            }
            return new Element(newvalues);
        }

Noten que el método soporta la multiplicación de permutaciones de diferentes tamaños.

Element.CreateIdentity genera un elemento identidad, de tamaño n.

Creando un swap de las dos primeras posiciones:

        public static Element CreateSwap(int size) 
        {
            Element element = CreateIdentity(size);
            element.values[0] = 1;
            element.values[1] = 0;
            return element;
        }

Creando un intercambio en una posición:

        public static Element CreateSwap(int size, int position)
        {
            Element element = CreateIdentity(size);
            element.values[position] = (byte) (position+1);
            element.values[position+1] = (byte) position;
            return element;
        }

Creando la rotación:

        public static Element CreateRotation(int size)
        {
            byte[] values = new byte[size];
            for (int k = 0; k < size; k++)
            {
                values[k] = (byte)(k == size - 1 ? 0 : k + 1);
            }
            return new Element(values);
        }

Un CompleteGroup es un grupo con todos sus elementos dados en el constructor:

    public class CompleteGroup : BaseGroup
    {
        private List<IElement> elements;
        public CompleteGroup(List<IElement> elements)
        {
            this.elements = elements.Distinct().ToList();
        }
//...
    }

Un GeneratedGroup es el resultado de combinar un conjunto de elementos generadores:

    public class GeneratedGroup : CompleteGroup
    {
        public GeneratedGroup(params IElement[] generators)
            : base(ElementUtilities.ElementsClosure(generators))
        {
        }
    }

ElementsUtilities.ElementsClosure es generada por todas las multiplicaciones (a(a*b, b*a, a*b*b, a*c*b… ) de los elementos iniciales presentados (a, b, c, …)

Notablemente, las permutaciones de S son generadas usando un swap y una rotación:

    public class SymmetricGroup : GeneratedGroup
    {
        public SymmetricGroup(int size)
            : base(Element.CreateSwap(size), Element.CreateRotation(size))
        {
        }
    }

Se puede probar que todo grupo finito es un subgrupo de un grupo generado por estos dos elementos: el llamado grupo simétrico de permutaciones de n elementos.

Como mencioné en el anterior post, hay otra implementación de grupos finitos en AjGroups: usando elementos abstractos, no permutaciones concretas. Seré el tema de un próximo post.

Nos leemos!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Leave a Reply

Your email address will not be published. Required fields are marked *