WARNING: The text below provides a guidance for a Project Euler problem.
If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.
If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.
If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.
Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.
Counting Binary Matrices
This amazingly set problem can provide a good learning opportunity. It tasks us with finding the number of binary matrices up to the equivalence where we proclaim two matrices equivalent if we can turn one into the other using some sequence of row/column swaps and row/column binary flips.
The core of the solution is the »Burnside’s lemma«; a group theoretic theorem used for example to find the number of states in which the Rubik’s cube can be in, up to the symmetries of the cube. It goes like this:
Let be a finite group acting on a set . For each let be the set of elements that fixes. Then:
Let be the set of all binary matrices and be the group of permissible operations on matrices that we are allowed to do (with the implicit group structure). That is:
where is the -th symmetric group (the group of all permutation of elements) and is the set of all subsets of . An element of looks like and signifies the following: flip all rows with indices in the set and permute the rows according to ; flip all columns with indices in and permute the columns according to .
We need to find , and by the Burnside’s lemma this is equal to . There are now two quantities that we need to compute. , which is easy:
and , which is harder. The key observation is that we can afford to be concerned only about the cycle types of the permutations; for any and with and of the same cycle type will fix the same number of matrices.
Let denote the number of permutations of cycle type , where under the cycle type we will understand with ; all ; for all (that is, is the sorted array of lengths of cycles present in a permutation). For example, the permutation of elements has the cycle type .
can be, after a simple combinatorial contemplation, computed as follows:
The denominator accounts for the order of two cycles of same length not having any importance. For each cycle in the cycle type, we consecutively choose of the remaining elements, which can give rise to distinct cycles. Then, for the main sum:
where as a small abuse of notation we write with being some permutation of cycle type and some permutation of cycle type .
Ignoring the flips for the time being, every pair of cycle types divides the matrix into “subarrays”, of sizes . In order for any matrix to be fixed by the permutations of these cycle types, every subarray is further divided into parts (the distinct orbits in the joint 2-dimensional permutation ), each of which must contain the same number everywhere. For each of these parts, we have two options (either we set the bit at every position within the part to or ), so any pair of cycle types fixes precisely matrices. The above sum becomes:
with being the number of permissible sets of flips of rows/columns, such that any two permutations of cycle types that fix a matrix, will also fix it after we flip rows indexed by and columns indexed by . We now turn into finding .
Let denote the number of indices of rows in the cycle that are flipped, and similarly, the number of indices of columns in the cycle that are flipped. The key realisation is that any flip sets are going to fix the matrix already fixed by permutations, as long as the following condition holds for all . The condition can be interpreted as: “When we successively apply on any element of the matrix, when it comes back to its original position, it must have undergone an even number of flips.”
In the binary world of ours, we can now consider the variables to be the unknowns and the above conditions specifying a system of linear equations. Let be the matrix representing this system of linear equations. That is, the -th condition specifies the row in the matrix :
Then simply (the exponent here is the number of free variables that we are left with).
All of the cycle types for a given can be precomputed quite easily.
Finding the rank of matrix (which I do not include here) and thus computing can be done in time, providing a solution which gives the full answer to the problem in about a second, on PyPy3.