Calculating number of permutations of a matrix with elements being adjacent integers only

Question

I'm trying to write a Python code in order to determine the number of possible permutations of a matrix where neighbouring elements can only be adjacent integer numbers. I also wish to know how many times each total set of numbers appears (by that I mean, the same numbers of each integer in n matrices, but not in the same matrix permutation)

Forgive me if I'm not being clear, or if my terminology isn't ideal! Consider a 5 x 5 zero matrix. This is an acceptable permutaton, as all of the elements are adjacent to an identical number.

0  0  0  0  0
0  0  0  0  0
0  0  0  0  0
0  0  0  0  0
0  0  0  0  0

25 x 0, 0 x 1, 0 x 2

The elements within the matrix can be changed to 1 or 2. Changing any of the elements to 1 would also be an acceptable permutation, as the 1 would be surrounded by an adjacent integer, 0. For example, changing the central [2,2] element of the matrix:

0  0  0  0  0
0  0  0  0  0
0  0  1  0  0
0  0  0  0  0
0  0  0  0  0


24 x 0, 1 x 1, 0 x 2

However, changing the [2,2] element in the centre to a 2 would mean that all of the elements surrounding it would have to switch to 1, as 2 is not adjacent to 0.

0  0  0  0  0
0  1  1  1  0
0  1  2  1  0
0  1  1  1  0
0  0  0  0  0

16 x 0, 8 x 1, 1 x 2

I want to know how many permutations are possible from that zeroed 5x5 matrix by changing the elements to 1 and 2, whilst keeping neighbouring elements as adjacent integers. In other words, any permutations where 0 and 2 are adjacent are not allowed.

I also wish to know how many matrices contain a certain number of each integer. For example, both of the below matrices would be 24 x 0, 1 x 1, 0 x 2. Over every permutation, I'd like to know how many correspond to this frequency of integers.

0  0  0  0  0        0  0  0  0  0
0  0  0  0  0        0  0  0  0  0
0  0  1  0  0        1  0  0  0  0
0  0  0  0  0        0  0  0  0  0
0  0  0  0  0        0  0  0  0  0

Again, sorry if I'm not being clear or my nomenclature is poor! Thanks for your time - I'd really appreciate some help with this, and any words or guidance would be kindly received.

Thanks, Sam

Answer 1

Just search for some more simple rules:
1s can be distributed arbitrarily in the array, since the matrix so far only consists of 0s. 2s can aswell be distributed arbitrarily, since only neighbouring elements must be either 1 or 2.

Thus there are f(x) = n! / x! possibilities to distributed 1s and 2s over the matrix.

So the total number of possible permutations is 2 * sum(x = 1 , n * n){f(x)}.

Calculating the number of possible permutations with a fixed number of 1s can easily be solved by simple calculating f(x).

The number of matrices with a fixed number of 2s and 1s is a bit more tricky. Here you can only rely on the fact that all mirrored versions of the matrix yield the same number of 1s and 2s and are valid. Apart from using that fact you can only brute-force search for correct solutions.

Answer 2

First, what you're calling a permutation isn't.

Secondly your problem is that a naive brute force solution would look at 3^25 = 847,288,609,443 possible combinations. (Somewhat less, but probably still in the hundreds of billions.)

The right way to solve this is called dynamic programming. What you need to do for your basic problem is calculate, for i from 0 to 4, for each of the different possible rows you could have there how many possible matrices you could have had that end in that row.

Add up all of the possible answers in the last row, and you'll have your answer.

For the more detailed count, you need to divide it by row, by cumulative counts you could be at for each value. But otherwise it is the same.

The straightforward version should require tens of thousands of operation. The detailed version might require millions. But this will be massively better than the hundreds of billions that the naive recursive version takes.