Group table completion program

The Further Maths syllabus incorporates group theory, a fairly useful but abstract concept. It’s all very interesting and somewhat reminiscent of our semi-formal introduction to set theory and functions with GL last year. Unfortunately, interesting as groups may be, exam questions can ask you to fill out a group table, a task whose tedium is comparable with plotting graphs with pen and paper. While completing a group table in class, after remarking that it’s somewhat similar to doing a SuDoku (each element appears exactly once in each column and row), I pointed out writing a computer program to do this would be interesting and much more fulfilling than bashing through a group table completion. And that’s exactly what I did.

The code is fairly self-explanatory but probably full of bad habits and other rubbish; the only reason I’m making a blog post about it is because it’s the first time I’ve ever implemented (albeit quite messily) a Breadth-First-Search-type algorithm for a vaguely realistic problem, making it particularly interesting (to me).

The algorithm for finding the value for a cell (derived from elements i and j, e.g. ij if the group is multiplicative) is basically this, in really loose structured English:

Concatenate i, j. Call this concatenation c.
Look up if c is an element of the group.
If so, done.
   Set c as the table’s value at (i,j).
Else: Add this expression to a previously empty list.
   Repeatedly:
      For each expression in the list:
         Find character sequences which can be simplified by examining the existing table
         For each of these simplifications
            Add the mono-simplified expression (simplified once) to the end of the list
            If this simplification is an element of the group, we’re done.
         Remove the expression from the list

In other words the simplification algorithm systematically takes the expression, finds lots of equivalent expressions (by looking up simplifications in the half-completed group table) and chooses the equivalent expression that happens to be an element of the group. This obviously requires closure, or the algorithm will keep searching forever and never complete. For this reason I implemented a counter-measure to infinite runtime – it’s a bit of a hack but hey…

The program prompts for input. The first line is N, the number of elements in the group. The next N lines are string representations of the elements, e.g. a, aa, ab, bba etc. The next N^2 lines are the existing table – the program needs something to start with to simplify anything.

Here’s my example test data:

6
e
a
aa
b
ab
aab
e
a
aa
b
ab
aab
a
-
e
aab
-
-
aa
e
-
ab
-
-
b
-
-
e
-
-
ab
-
-
-
-
-
aab
-
-
-
-
-

This represents the following group table:

e   a   aa  b   ab  aab
a   -   e   aab -   -
aa  e   -   ab  -   -
b   -   -   e   -   -
ab  -   -   -   -   -
aab -   -   -   -   -

The program’s output is:

e   a   aa  b   ab  aab
a   aa  e   aab b   ab
aa  e   a   ab  aab b
b   ab  aab e   a   aa
ab  aab b   aa  e   a
aab b   ab  a   aa  e

Incidentally this is (hopefully) the answer to one of the questions set for this week’s homework.

Here’s the C#.NET code:

using System;
using System.Collections;
using System.Linq;
using System.Text;

namespace Groups
{
    class Program
    {
        public static string[] elements;
        public static int[,] table;
        public static int N;
        public static int depth;
        public static ArrayList simplifications = new ArrayList();

        static void Main(string[] args)
        {
            Console.WriteLine("Size of group");
            N = Convert.ToInt32(Console.ReadLine());

            elements = new string[N];
            Console.WriteLine("Group elements");
            for (int n = 0; n < N; n++) elements[n] = Console.ReadLine();

            table = new int[N,N];
            Console.WriteLine("Existing group table:");
            for (int j = 0; j < N; j++)
            {
                Console.WriteLine("row " + j.ToString());
                for (int i = 0; i < N; i++)
                    table[i, j] = str2index(Console.ReadLine());
            }

            PrintTable();

            while (true)
            {
                Console.ReadKey();

                FillTable();
                PrintTable();
            }
        }

        public static void PrintTable()
        {
            for (int j = 0; j < N; j++)
            {
                Console.WriteLine();
                for (int i = 0; i < N; i++)
                {
                    if (table[i, j] == -1) Console.Write("-   ");
                    else
                    {
                        Console.Write(elements[table[i, j]]);
                        for (int a = 0; a < 4 - elements[table[i, j]].ToString().Length; a++) Console.Write(" ");
                    }
                }
            }
            Console.WriteLine();
        }

        public static void FillTable()
        {
            // for each thing:
                // concatenate strings
                // look up if concatenation is an element. If so, done.
                // else look up from table if part of concatenation simplifies.
                // search through all simplifications until one which is an elment is found

            for (int i = 0; i < N; i++)
            {
                Console.WriteLine("now doing row " + i);
                for (int j = 0; j < N; j++)
                {
                    if (table[i, j] == -1)
                    {
                        string s = elements[i] + elements[j];
                        if (str2index(s) != -1)
                        {
                            table[i, j] = str2index(s);
                        }
                        else
                        {
                            simplifications = new ArrayList();
                            simplifications.Add(s);
                            depth = 0;
                            Simplify();
                            table[i, j] = str2index((string)simplifications[0]);
                        }
                    }
                }
            }

        }

        /// <summary>
        /// Simplifies the single element in simplifications.
        /// When done, will leave a single element simplifications[0] in simplifications.
        /// That will be the simplified string, which is hopefully an element.
        /// Told you it's a messy implementation
        /// </summary>
        public static void Simplify()
        {
            depth++;

            if (depth > 20 || simplifications.Count > 1000)
            {
                simplifications = new ArrayList();
                simplifications.Add("-");
                return;
            }

            int origsize = simplifications.Count;
            Console.WriteLine(origsize);
            string ret = "!";

            for (int q=0; q<origsize; q++)
            {
                string[] simps = simplify((string)simplifications[q]);
                foreach (string t in simps)
                    if (str2index(t) != -1) ret = t;
                foreach (string t in simps)
                {
                    if (!simplifications.Contains(t)) simplifications.Add(t);
                }
            }

            for (int a = 0; a < origsize; a++) simplifications.RemoveAt(0);
            if (ret != "!")
            {
                simplifications = new ArrayList();
                simplifications.Add(ret);
            }
            else Simplify();
        }

        /// <summary>
        /// Finds all single-step simplifications of a string
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static string[] simplify(string s)
        {
            string[] ret = new string[1000];
            int n = 0;
            for (int startat = 0; startat < s.Length - 1; startat++)
            {
                for (int a = 0; a < N; a++) // first element
                {
                    if (s.Length >= startat + elements[a].Length)
                    {
                        if (s.Substring(startat, elements[a].Length) == elements[a])
                        {
                            for (int b = 0; b < N; b++) // second element
                            {
                                if (s.Length >= startat + elements[a].Length + elements[b].Length)
                                {
                                    if (s.Substring(startat + elements[a].Length, elements[b].Length) == elements[b])
                                    {
                                        if (table[a, b] != -1)
                                        {
                                            ret[n++] = s.Substring(0, startat) +  elements[table[a, b]] + s.Substring(startat + elements[a].Length + elements[b].Length);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            string[] realret = new string[n];
            for (int a = 0; a < n; a++) realret[a] = ret[a];
            return realret;
        }

        public static int str2index(string str)
        {
            for (int a=0; a<elements.Length; a++)
            {
                if (elements[a] == str) return a;
            }
            return -1;
        }
    }
}

Advertisements

2 Responses to Group table completion program

  1. […] that work for the A2 computing project, did some really cool (theory-based) personal projects (1, 2), was invited to the next round of the British Informatics Olympiad (which I unwillingly turned […]

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

%d bloggers like this: