Angel \”Java\” Lopez on Blog

January 3, 2011

Permutations in AjGroups

Filed under: .NET, AjGroups, C Sharp, Open Source Projects — ajlopez @ 9:30 am

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];
                    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


  1. […] Presenting AjGroups: Finite Groups Library Permutations in AjGroups […]

    Pingback by Abstract Elements in AjGroups « Angel “Java” Lopez on Blog — January 5, 2011 @ 10:41 am

  2. […] Presenting AjGroups: Finite Groups Library Permutations in AjGroups […]

    Pingback by Elementos abstractos en AjGroups - Angel "Java" Lopez — January 6, 2011 @ 9:34 am

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at

%d bloggers like this: