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