Matrix permutation

I came across this interesting problem when I was solving a coursera assignment (8-puzzle) on Algorithms & Data Structures. This isn't related to the 8-puzzle where you need to visualize the solution as a game tree data structure.

I think this is related to the game tree.

Consider you have a \(2 \times 2\) grid where there is an \(X\) in one of the squares. You can make children of that figure only by moving \(X\) it to the adjacent square either left, right, top, bottom. How many iterations do I need to ensure that \(X\) has been through all the locations. It is possible that you can get the \(X\) in a previous position by making a child of child (from the previous iteration: avoid such repetition.

Here is a figure that shows the case for the grid in question:

This is a very trivial example. What could be the solution for a larger grid?

writing code for doing combinations

Combination is a common problem in mathematics which deals with different ways via which we can select r objects given n, where r < n. So we have n distinct objects and we can't have repetitions. For e.g., if we are to select 3 letters from the string ABCD, we have the following

ABC
ABD
ACD
BCD

So there are a total of 4 ways of selecting 3 objects.

Perfectly follows the formula,
\[{n \choose r} = \frac{n!}{r! \times (n-r)!}\]
A more simplified version of the above formula is,
\[{n \choose r}= \frac{n(n-1)(n-2)...(n-r+1)}{r!}\]
This is actually better for computations.

But how to write code to output the various selection as we've done above?

I'd take to pseudo code but you can't implement the pseudo code in one language and see the results immediately. Hence I've taken to python. I am not python-biased...I just like the simplicity of expressing logic. It models pseudo code fairly well...

There are better ways to write this...you can use a generator instead of a loop that creates and returns an array. "Generator" is a concept that is available on most of the popular programming languages. You can explore my other gists to see how this is done in python and java.

Meanwhile, happy programming.