# Permutations in AjGroups

In my previous post I presented AjGroups, a class library written in C# that implements finite group concepts and operations. Source code at my AjCodeKata Google Project, under trunk/AjGroups.

In this post, I want to explain one of the implementations inside AjGroups: groups based on permutation.

A permutation is a bijective application of a set S over S. Say S is

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

Then, an permutation example is:

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

It is the identity permutation. Other example:

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

It is a swap, interchange of the first two elements. A rotation permutation:

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

Permutations can be combined r*s:

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

The permutations of S are the elements of a group using the * operation. AjGroups implements a permutation using the Element class:

```    public class Element : AjGroups.IElement
{
private byte[] values;
public Element(params byte[] values)
{
//....
}
The permutation is represented in a byte array, where values[k] is the result of f(k), being f the permutation represented by the Element.
Element.Multiply(Element element) implements the multiplication:

Element.CreateIdentity generates an identity element, of size 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);
}
Note that the method supports the multiplication of different size permutations.
Creating a swap of first two positions:
public static Element CreateSwap(int size)
{
Element element = CreateIdentity(size);
element.values[0] = 1;
element.values[1] = 0;
return element;
}

Creating a swap at position:
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;
}

Creating a rotation:
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);
}

A CompleteGroup is a group with all its elements given in the constructor:
public class CompleteGroup : BaseGroup
{
private List<IElement> elements;
public CompleteGroup(List<IElement> elements)
{
this.elements = elements.Distinct().ToList();
}
//...
}
A GeneratedGroup is the result of combining a set of generator elements:
public class GeneratedGroup : CompleteGroup
{
public GeneratedGroup(params IElement[] generators)
: base(ElementUtilities.ElementsClosure(generators))
{
}
}

ElementsUtilities.ElementsClosure generated by all the multiplication (a(a*b, b*a, a*b*b, a*c*b… ) generated by a set of initial elements (a, b, c, …)
Notably, the permutations of S are generated using a swap and a rotation:
public class SymmetricGroup : GeneratedGroup
{
public SymmetricGroup(int size)
: base(Element.CreateSwap(size), Element.CreateRotation(size))
{
}
}

It can be proved that every finite group is a subgroup of a group generated by those two elements: a symmetric group of order n.
As I mentioned in my previous post, there is another implementation of finite groups in AjGroups: using abstract elements, not concrete permutations. That will be the topic for upcoming post.
Keep tuned!
Angel “Java” Lopez
http://www.ajlopez.com