December 2014

[Xyzzy]

http://domino.research.ibm.com/Comm/...ember2014.html

[alpertron]

Originally Posted by Xyzzy

http://domino.research.ibm.com/Comm/...ember2014.html

I've made a fast approach by computing all binary matrix combinations of 4x5 and 3x6, sorting them and then count the repeated results. In no case there are 29 occurrences. It appears that the matrix must have a different size.

The program in Visual Studio 98 is:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[])
{
  char oldstr[100];
  char newstr[100];
  int a,b,c,d,e,f,g,h,i,j;
  int count = 0;
  FILE *fpFile = fopen("test", "wt");
#if 0
  for (a=0; a<1048576; a++)
  {
    b = ((a >> 19) & 1) + ((a >> 15) & 1) + ((a >> 11) & 1) + ((a >> 7) & 1) + ((a >> 3) & 1);
    c = ((a >> 18) & 1) + ((a >> 14) & 1) + ((a >> 10) & 1) + ((a >> 6) & 1) + ((a >> 2) & 1);
    d = ((a >> 17) & 1) + ((a >> 13) & 1) + ((a >> 9) & 1) + ((a >> 5) & 1) + ((a >> 1) & 1);
    e = ((a >> 16) & 1) + ((a >> 12) & 1) + ((a >> 8) & 1) + ((a >> 4) & 1) + (a & 1);
    f = ((a >> 19) & 1) + ((a >> 18) & 1) + ((a >> 17) & 1) + ((a >> 16) & 1);
    g = ((a >> 15) & 1) + ((a >> 14) & 1) + ((a >> 13) & 1) + ((a >> 12) & 1);
    h = ((a >> 11) & 1) + ((a >> 10) & 1) + ((a >> 9) & 1) + ((a >> 8) & 1);
    i = ((a >> 7) & 1) + ((a >> 6) & 1) + ((a >> 5) & 1) + ((a >> 4) & 1);
    j = ((a >> 3) & 1) + ((a >> 2) & 1) + ((a >> 1) & 1) + (a & 1);
    fprintf(fpFile, "[%d %d %d %d] [%d %d %d %d %d]\n",b,c,d,e,f,g,h,i,j);
  }
#endif
  for (a=0; a<262144; a++)
  {
    b = ((a >> 17) & 1) + ((a >> 14) & 1) + ((a >> 11) & 1) + ((a >> 8) & 1) + ((a >> 5) & 1) + ((a >> 2) & 1);
    c = ((a >> 16) & 1) + ((a >> 13) & 1) + ((a >> 10) & 1) + ((a >> 7) & 1) + ((a >> 4) & 1) + ((a >> 1) & 1);
    d = ((a >> 15) & 1) + ((a >> 12) & 1) + ((a >> 9) & 1) + ((a >> 6) & 1) + ((a >> 3) & 1) + (a & 1);
    e = ((a >> 17) & 1) + ((a >> 16) & 1) + ((a >> 15) & 1);
    f = ((a >> 14) & 1) + ((a >> 13) & 1) + ((a >> 12) & 1);
    g = ((a >> 11) & 1) + ((a >> 10) & 1) + ((a >> 9) & 1);
    h = ((a >> 8) & 1) + ((a >> 7) & 1) + ((a >> 6) & 1);
    i = ((a >> 5) & 1) + ((a >> 4) & 1) + ((a >> 3) & 1);
    j = ((a >> 2) & 1) + ((a >> 1) & 1) + (a & 1);
    fprintf(fpFile, "[%d %d %d] [%d %d %d %d %d %d]\n",b,c,d,e,f,g,h,i,j);
  }
  fclose(fpFile);
  system("sort <test >test2");

  fpFile = fopen("test2", "rt");
  oldstr[0] = 0;
  while (!feof(fpFile))
  {
    fgets(newstr, 100, fpFile);
    if (strcmp(newstr, oldstr))
    {
      if (count == 29)
      {
        printf("%s", oldstr);
      }
      count = 0;
      strcpy(oldstr, newstr);
    }
    count++;
  }
}

[TheMawn]

It says to limit the search to matrices with 50 or less bits. 4x5 and 3x6 are but a fraction of all allowable matrices.

The biggest are

2x25
3x16
4x12
5x10
6x8
7x7

But there are still tens of others. 5x9, 5x8, 5x7, 5x6, etc..

I'm trying to think of a way to not brute-force this problem, because a 7x7 matrix gives 2⁴⁹ combinations to check.

[TheMawn]

The first thing I see is that a matrix with any one row or column with all the same numbers is essentially equivalent to the same matrix, but without that row or column in it.

For example

								1	1	1	1		4	
0	0	0	1		1			0	0	0	1		1
1	0	0	1		2			1	0	0	1		2
1	0	1	1		3			1	0	1	1		3
1	0	0	0		1			1	0	0	0		1
														
3	0	1	3					4	1	2	4

Note that adding the top row of 1's had no bearing on the sums of all the other rows and only increased each column sum by 1. If you couldn't find 29 identical sums in a 4x4 matrix, any 5x4 with a row of 1's or 0's and any 4x5 matrix with a column of 1's or 0's will also not give you 29 identical sums, because the sums are "equivalent" in that sense.

If you think about it, you could begin with a 2x2 matrix and work outward in any direction to reach any size you want, using the logic that adding a row or column of 1's or 0's would not grant any new solutions. If that is the case, then you can eliminate any matrices with rows or columns where the elements are all the same from your search, assuming you started from a smaller matrix.


Again, just to make myself clear: A matrix of any size (for example, 5x4) which contains a row or column where all the elements are the same (for example a row of 1's) can be considered equivalent to that same matrix without the row or column (so a 4x4 matrix) because the sums are affected in a very predictable way. The row of 1's always has a sum of 4 and the sums of columns are always just 1 bigger, so any 5x4 matrix where the top row is all 1's will not give 29 identical sums if a 4x4 matrix (without the row of 1's) does not give 29 identical sums.

Thus, if you very methodically checked all 3x6 matrices, then you can eliminate all 3x7 and 4x6 matrices with rows or columns with all the same element from your search.

[science_man_88]

Originally Posted by TheMawn

I'm trying to think of a way to not brute-force this problem, because a 7x7 matrix gives 2⁴⁹ combinations to check.

Hint:

I think I have a way to simplify it a bit but (I'm trying currently in my head only) which rows in says a n by m matrix are able to be moved to cover where the other one used to occupy ex:

[1 0 1] <- move one left
[0,1,0] <- one left as well

result:

[0 1 1]
[1,0,0]

because if I thought about it correctly it's a sum of the number of exchanges possible that has to add to 29.

[alpertron]

I extended the program to handle 5x5 matrices as follows:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[])
{
  char oldstr[100];
  char newstr[100];
  int a,b,c,d,e,f,g,h,i,j,k;
  int count = 0;
  FILE *fpFile = fopen("test", "wt");
  for (a=0; a<33554432; a+=2)
  {
    b = ((a >> 24) & 1) + ((a >> 19) & 1) + ((a >> 14) & 1) + ((a >> 9) & 1) + ((a >> 4) & 1);
    c = ((a >> 23) & 1) + ((a >> 18) & 1) + ((a >> 13) & 1) + ((a >> 8) & 1) + ((a >> 3) & 1);
    d = ((a >> 22) & 1) + ((a >> 17) & 1) + ((a >> 12) & 1) + ((a >> 7) & 1) + ((a >> 2) & 1);
    e = ((a >> 21) & 1) + ((a >> 16) & 1) + ((a >> 11) & 1) + ((a >> 6) & 1) + ((a >> 1) & 1);
    f = ((a >> 20) & 1) + ((a >> 15) & 1) + ((a >> 10) & 1) + ((a >> 5) & 1);

    g = ((a >> 24) & 1) + ((a >> 23) & 1) + ((a >> 22) & 1) + ((a >> 21) & 1) + ((a >> 20) & 1);
    h = ((a >> 19) & 1) + ((a >> 18) & 1) + ((a >> 17) & 1) + ((a >> 16) & 1) + ((a >> 15) & 1);
    i = ((a >> 14) & 1) + ((a >> 13) & 1) + ((a >> 12) & 1) + ((a >> 11) & 1) + ((a >> 10) & 1);
    j = ((a >> 9) & 1) + ((a >> 8) & 1) + ((a >> 7) & 1) + ((a >> 6) & 1) + ((a >> 5) & 1);
    k = ((a >> 4) & 1) + ((a >> 3) & 1) + ((a >> 2) & 1) + ((a >> 1) & 1);
    fprintf(fpFile, "[%d %d %d %d %d] [%d %d %d %d %d]\n",b,c,d,e,f,g,h,i,j,k);
    fprintf(fpFile, "[%d %d %d %d %d] [%d %d %d %d %d]\n",b,c,d,e,f+1,g,h,i,j,k+1);
  }
  fclose(fpFile);
  system("sort test /O test2");

  fpFile = fopen("test2", "rt");
  oldstr[0] = 0;
  while (!feof(fpFile))
  {
    fgets(newstr, 100, fpFile);
    if (strcmp(newstr, oldstr))
    {
      if (count == 29)
      {
        printf("%s", oldstr);
      }
      count = 0;
      strcpy(oldstr, newstr);
    }
    count++;
  }
}

I attached the solutions found by the program.

Obviously these 1800 solutions can be reduced by taking into account the permutations.

[Drdmitry]

Some variation of dynamic programming will do the job.
I found 8 non-equivalent solutions (up to permutation of rows and columns and up to adding lines full of zeroes or ones). But if one notices that all of them go in pairs (one can flip all zeroes to ones and vice versa) then there are four non-equivalent solutions.

[alpertron]

Do your 8 solutions cover all 1800 solutions found by my program?

[alpertron]

I'm attaching all 2880 solutions for the 4x6 binary matrix case.

I ran the program one more time, for 3x8 binary matrix, but it found no solutions.

[Drdmitry]

Originally Posted by Drdmitry

Some variation of dynamic programming will do the job.
I found 8 non-equivalent solutions (up to permutation of rows and columns and up to adding lines full of zeroes or ones). But if one notices that all of them go in pairs (one can flip all zeroes to ones and vice versa) then there are four non-equivalent solutions.

I computed only 3 * n (n <= 16) and 4 * n (n <= 12) cases, so my solutions do not cover that in result file.
I have looked at your result file. Up to permutations of rows and columns it actually contains two non-equivalent solutions. And up to flipping all zeroes to ones and vice versa there is essentially one solution there.

[axn]

Originally Posted by alpertron

Do your 8 solutions cover all 1800 solutions found by my program?

I see only two unique solutions to the 5x5 case (in the results file):

[1 1 3 3 4] [1 1 3 3 4]
[1 2 2 4 4] [1 2 2 4 4]

Everything else is a permutation: 30 permutations for each row x 30 permutations for each column x 2 sets = 1800.

EDIT:-
Same for 4x6 case

[1 2 3 5] [1 1 1 2 3 3]
[1 3 4 5] [1 1 2 3 3 3]

24 perm x 60 perm x 2 sets = 2880

Also, even the two unique solutions aren't unique!! They're obtained from each other by swapping 1's and 0's. So net effect, there is only one unique solution for each class!