6
$\begingroup$

The general problem

Given a matrix, I would like to permute the order of values in each row, so that all the columns of the matrix sums to the same value.

A simple example

For example, given:

 0     0     2     6  0     0     6    18  0     0    10    30  0     0    14    42  0     0    18    54  0     0    22    66 

One solution is:

 0     0     2     6  0    18     6     0 30     0    10     0 42     0    14     0  0    54    18     0  0     0    22    66 

Notice that each column sums to 72. Of course, the solution is not unique; one may permute the columns themselves to obtain different solutions, such as:

 0     0     2     6 18     0     6     0  0    30    10     0  0    42    14     0 54     0    18     0  0     0    22    66 

The specific problem

Here I am looking at a simple $30 \times 5$ matrix. The matrix is defined thus: the contents of row $n$ is $[0, 0, 2f(n), 6f(n), 12f(n)+2]$ where $f(n) = 4n^2+4n+1$ and $n = 0, 1, 2, ...,29$.

Here is what the matrix looks like:

       0           0           2           6          14        0           0          18          54         110        0           0          50         150         302        0           0          98         294         590        0           0         162         486         974        0           0         242         726        1454        0           0         338        1014        2030        0           0         450        1350        2702        0           0         578        1734        3470        0           0         722        2166        4334        0           0         882        2646        5294        0           0        1058        3174        6350        0           0        1250        3750        7502        0           0        1458        4374        8750        0           0        1682        5046       10094        0           0        1922        5766       11534        0           0        2178        6534       13070        0           0        2450        7350       14702        0           0        2738        8214       16430        0           0        3042        9126       18254        0           0        3362       10086       20174        0           0        3698       11094       22190        0           0        4050       12150       24302        0           0        4418       13254       26510        0           0        4802       14406       28814        0           0        5202       15606       31214        0           0        5618       16854       33710        0           0        6050       18150       36302        0           0        6498       19494       38990        0           0        6962       20886       41774 

Obviously, the desired sum for each column is equal to the sum of all elements in the matrix divided by the number of columns. Here it is $\frac{1}{5}\left(60 + 20\sum_{n=0}^{29} f(n)\right) = 143972$.

We certainly cannot do this by brute force: For an $m\times n$ matrix the number of possibilities are: $(n!)^m$ which combinatorially explodes. Here, two of the columns given are zeros so we have $\left(\frac{n!}{2}\right)^m$ unique ways to permute the values of each row - which is not much better.

Fortunately, this matrix has a well-defined pattern to it, and I am wondering: can this pattern can be exploited to derive solutions more easily?

EDIT: I have made a recursive depth-first search to find solutions. On each iteration, it attempts to construct a vector that sums to the desired result (in this case 143972) by choosing each entry in the vector from a different row in the matrix. Once one such vector has been created, it removes the chosen entries from the matrix thereby changing it from an $m\times n$ matrix to an $m \times n-1$ one. This repeats until either no solution can be found, or a the matrix becomes empty. In the worst case, it runs on the order of $n^m$ for an $m\times n$ matrix (but it turns out that finding one solution is fast because my matrix has many, many solutions apparently).

Here are three sample solutions I have found using this approach:

Solution 1

       6          14           0           0           2        0          54          18         110           0       50           0           0         302         150        0           0          98         590         294        0           0         162         486         974        0           0         242        1454         726      338           0        1014           0        2030        0         450           0        2702        1350        0           0         578        1734        3470        0           0         722        2166        4334        0           0         882        2646        5294        0           0        1058        3174        6350        0           0        1250        3750        7502        0           0        1458        4374        8750        0           0        1682        5046       10094        0           0        1922       11534        5766        0        2178           0        6534       13070        0           0        2450        7350       14702        0           0        2738       16430        8214        0           0        3042       18254        9126     3362           0       20174       10086           0        0        3698       22190       11094           0        0       12150       24302        4050           0        0       26510       13254        4418           0        0       28814       14406        4802           0    31214       15606        5202           0           0    33710       16854        5618           0           0    36302       18150        6050           0           0    38990       19494        6498           0           0        0           0        6962       20886       41774 

Solution 2

       6           0           2           0          14        0         110           0          54          18        0         150           0          50         302      294         590           0           0          98      486         974           0         162           0      726         242        1454           0           0     1014        2030           0         338           0     2702         450        1350           0           0     1734        3470         578           0           0     4334        2166         722           0           0     5294        2646         882           0           0     3174        6350        1058           0           0     7502        3750        1250           0           0     8750        4374           0        1458           0    10094        5046        1682           0           0    11534        5766        1922           0           0    13070        6534        2178           0           0    14702        7350        2450           0           0    16430        8214        2738           0           0    18254        9126        3042           0           0    20174       10086        3362           0           0     3698       22190       11094           0           0        0       24302       12150        4050           0        0       13254       26510           0        4418        0        4802       28814       14406           0        0           0       15606       31214        5202        0           0        5618       33710       16854        0           0        6050       18150       36302        0           0        6498       19494       38990        0           0        6962       20886       41774 

Solution 3

       0          14           0           6           2        0          18         110           0          54        0           0         302         150          50        0         590         294          98           0      162         974           0         486           0     1454         242         726           0           0        0        1014        2030         338           0      450        1350        2702           0           0        0        1734        3470           0         578      722        4334        2166           0           0        0        2646        5294         882           0     1058        3174        6350           0           0        0        3750        7502        1250           0     1458        4374        8750           0           0        0        5046       10094        1682           0     5766       11534        1922           0           0     2178           0       13070        6534           0     7350       14702        2450           0           0        0        2738        8214       16430           0    18254        9126        3042           0           0        0        3362       10086       20174           0    11094       22190        3698           0           0        0        4050       12150       24302           0    26510       13254        4418           0           0        0           0        4802       14406       28814    31214       15606        5202           0           0        0           0        5618       16854       33710    36302       18150        6050           0           0        0           0        6498       19494       38990        0           0        6962       20886       41774 

But I still don't know whether there's a way to count the number of solutions, or how to generate more solutions more efficiently. And my depth-first-search algorithm is a rather brute-force way that doesn't take advantage of the known sequence that the original matrix is made up of.

1 Answers 1

2

You can construct your "vector" using dynamic programing. Let $g(i, j) = x$ represents "There are $x$ ways to satisfy $\sum_{r=0}^i A(r, c(r)) = j$, where $ c(r) = 0, 1, 2, 3, m-1$ ". Then $ g(i, j) = \sum_{k=0}^{m-1} g(i - 1, j - A(i, k)) $ In this way you can find the number of all valid "vector" in time $O(n^3 m)$. In your example, the number is 4053803829558. Similarly, you can also use this method to construct the vector.