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

http://twitter.com/ajlopez

2 Comments »

  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:

WordPress.com Logo

You are commenting using your WordPress.com 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

The Shocking Blue Green Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 65 other followers

%d bloggers like this: