Permutations and brute force

I was writing a computer program version of an old South Indian mathematical strategy game known as Pallankuzhi and it was then that I faced the problem of how to create a computer player that would play the game. While I have not made much headway into that yet (have to read more about graphs and linking boards with similar configurations), I decided to revisit Tic Tac Toe.

While I have written a program in the past (with a computer vs. human and computer vs. computer option), I had not paid much attention to the theory of using brute force. A question like how many (legal and illegal) games are there and how to enumerate them did not cross my mind then. I don’t think such a question ever comes up in normal software programming. I thought over the problem for a couple of days and finally came up with something. While it is not the most efficient implementation, it does the job.

The code is more or less self explanatory. But let me explain the logic behind it anyway. Consider a string ‘abcd’. Since there are four elements, there are 4! (read four factorial) different permutations = 4*3*2*1 = 24. I use i, j, k and l as indices into the string and the permutations are as follows.

abcd (i = 0, j = 1, k = 2, l = 3)
abdc (i = 0, j = 1, k = 3, l = 2)
acdb (i = 0, j = 2, k = 3, l = 1)
acbd (i = 0, j = 2, k = 1, l = 3)
adbc (i = 0, j = 3, k = 1, l = 2)
adcb (i = 0, j = 3, k = 2, l = 1)

bcda (i = 1, j = 2, k = 3, l = 0)
bcad (i = 1, j = 2, k = 0, l = 3)
bdac (i = 1, j = 3, k = 0, l = 2)
bdca (i = 1, j = 3, k = 2, l = 0)
bacd (i = 1, j = 0, k = 2, l = 3)
badc (i = 1, j = 0, k = 3, l = 2)

cdab (i = 2, j = 3, k = 0, l = 1)
cdba (i = 2, j = 3, k = 1, l = 0)
cabd (i = 2, j = 0, k = 1, l = 3)
cadb (i = 2, j = 0, k = 3, l = 1)
cbda (i = 2, j = 1, k = 3, l = 0)
cbad (i = 2, j = 1, k = 0, l = 3)

dabc (i = 3, j = 0, k = 1, l = 2)
dacb (i = 3, j = 0, k = 2, l = 1)
dbca (i = 3, j = 1, k = 2, l = 0)
dbac (i = 3, j = 1, k = 0, l = 2)
dcab (i = 3, j = 2, k = 0, l = 1)
dcba (i = 3, j = 2, k = 1, l = 0)

As expected, a pattern emerges (note that I am using positive modular arithmetic where 0 – 1 = 3 in this case as the figures are mod 4).

  1. i goes from 0 to 3.
  2. Within each section of size 6 where i remains constant, j goes from i + 1 to i – 1.
  3. Within each section of size 2 where j remains constant, k goes from j + 1 to the first ‘non i’ j – 1.
  4. And, finally, within each section of size 1 where k remains constant, l will be the first ‘non i’, ‘non j’ k + 1 or k – 1 which are the same.

Put this information into a recursive function and you have your algorithm.

Some good links which discuss permutations in depth and also provide better algorithms –
Bear Cave: Calculating Permutations
Permutation Algorithms Using Iteration and the Base-N-Odometer Model (Without Recursion)

Also, an analysis of Tic Tac Toe.

Advertisements
Trackbacks are closed, but you can post a comment.

Comments

  • Praveen Santosh  On November 9, 2012 at 9:02 am

    sir, kindly gimme t c progarm for Pallankuzhi permutation………………….

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