Efficient Indexing method for a 2 by 2 matrix

Question

If I fill numbers from 1 to 4 in a 2 by 2 matrix, there are 16 possible combinations. What I want to do is store values in an array of size 24 corresponding to each matrix. So given a 2 by 2 matrix, I want a efficient indexing method to index into the array directly.( I dont want comparing all 4 elements for each of 16 positions). Something similar to bit vector ? but not able to figure out how? I want it for a 4 by 4 matrix also filling from 1 to 9

Answer 1

to clarify: you're looking for an efficient hash function for 2x2 matrices. you want to use the results of the hash function to compare matrices to see if they're the same.

first, lets assume you actually want the numbers 0 to 3 instead of 1 to 4 - this makes it easier, and is more computer-sciency. Next, 16 is not right. there are 24 possible permutations of the numbers 0-3. There are 4^4 = 256 possible strings of length 4 that use a four-letter alphabet (you can repeat already-used numbers).

either one is trivial to encode into a single byte. Let the first 2 bits represent the (0,0) position, the next 2 bits represent (0,1), and so forth. Than, to hash your 2x2 matrix, simply do:

hash = m[0][0] | (m[0][1] << 2) | (m[1][0] << 4) | (m[1][1] << 6

random example: the number 54 in binary is 00110110 which represents a matrix like:

2 1
3 0

Answer 2

When you need efficiency, sometimes code clarity goes out the window :)

First you need to be sure you want efficiency - you have profiling info to be sure that the simple comparison code is too inefficient for you?

---

You can simply treat it as an array of bytes of the same size. memcmp does comparisons of arbitary memory:

A data structure such as:

int matrix[2][2];

is stored the same as:

int matrix[2*2];

which could be dynamically allocated as:

typedef int matrix[2*2];
matrix* m = (matrix*)malloc(sizeof(matrix));

I'm not suggesting you dynamically allocate them, I'm illustrating how the bytes in your original type is actually layed out in memory.

Therefore, the following is valid:

matrix lookup[16];

int matrix_cmp(const void* a,const void* b) {
   return memcmp(a,b,sizeof(matrix));
}

void init_matrix_lookup() {
   int i;
   for(i=0; i<16; i++) {
      ...
   }
   qsort(lookup,16,sizeof(matrix),matrix_cmp));
}

int matrix_to_lookup(matrix* m) {
   // in this example I'm sorting them so we can bsearch;
   // but with only 16 elements, its probably not worth the effort,
   // and you could safely just loop over them...
   return bsearch(m,lookup,16,sizeof(matrix),matrix_cmp);
}