match an array with a given set of arrays We have a set of 24 distinct arrays, each array has 36 elements and each element can have one of 13 possible values.

Then we're given an array X (this array is certainly part of our set) and we have to find to which array of our set it corresponds to.

Of course, we can check all 36 elements of X against each of 36 elements of our 24 arrays and find out with which it corresponds to.

I'm trying to reduce this number of 36 comparisons.

My naive approach is something like this:


Take all possible subsets of 0..35, except the empty subset.
Each of this subsets denotes which elements we should compare.
Use each of this subsets with input all the 24 arrays of our given set and check which of these subsets produce as output the given set of our 24 arrays, these are valid subsets.
From these valid subsets, the one with the fewer elements is our solution.


Unfortunately, all possible subsets of 0..35 excluding the empty subset is $2^{36}-1$

I was wondering if there could be another approach to the problem.

Many different arrays X will be matched against the given set of 24 arrays so any preprocessing of the 24 arrays is really worth the effort.

User JarkkoL suggested to precompute CRC32 of the set of the given arrays and then compare with the CRC32 of the array X. 

Still, I'm wondering if there's a smart way not to calculate CRC32 for the whole array. I'm looking for the smallest possible number of elements for which I should compute it.
You could calculate something like crc32 of the arrays and compare them with the crc32 of the new array. If the crc32's of the arrays match then you can do further check if the elements actually match (in case there is crc32 collision, which is very rare). If you know the new array exists in the set, you could select crc32 seed value which avoids the crc32 collisions, so once you find the crc32 match you can be sure it's the correct one without comparing the elements at all (just test max 24 ints). You could try something more lightweight than crc32 too if that's a performance issue.

If you would really want to push this, you could then sort the arrays by the checksum value and find the matching checksum with binary search, thus cutting the number of comparisons to log2(24)=5. Maybe not worth it for such a small amount of arrays though.