3
$\begingroup$

English is not my native language: sorry for my mistakes. Thank you in advance for your answers.

Two Bijections and an Array...


The duplication problem

Here is a 2D array (in this particular example: rows: 1 to 4; columns: A to D) nonrandomly and nonarbitrary filled with integers.

$$ \left[ \begin{array}{cc|cc} 7 & 1 & 1 & 7 \\ 4 & 4 & 1 & 1 \\ 5 & 1 & 1 & 5 \\ 3 & 3 & 5 & 5 \end{array} \right]. $$

These numbers can be handled, but only one kind of move is allowed: You can move the numbers on the left or the right in each row, but you cannot shuffle them and you cannot move them vertically.

Example (first row):

  • Right: 7 1 1 7 → 7 7 1 1 (shift)

  • Wrong: 7 1 1 7 → 7 1 7 1 (shuffle)

By the nature of the data in this model (here is the nonrandom and nonarbitrary part), it is possible to have the same number of identical integers in columns A and B, and in column C and D, respectively. In other words, two bijections (or perfect one-to-one correspondences).

That is: if you have 3 '1' in column A, then you need to have 3 '1' in column B, and so on, in order to have a solution.

An example is worth a thousand words. Applying allowed moves on our array, we can produce this result:

$$ \left[ \begin{array}{cc|cc} 1 & 1 & 7 & 7 \\ 1 & 1 & 4 & 4 \\ 1 & 1 & 5 & 5 \\ 3 & 3 & 5 & 5 \end{array} \right]. $$

It is easy to see that columns A and B share the same number of identical integers (1, 3), and columns C and D, too (7, 4, 5).

Then, a solution is valid when there is a perfect one-to-one correspondence between the numbers of A and B (bijection 1), regardless their order, on the one side; as well as a perfect one-to-one correspondence between the numbers of C and D (bijection 2), regardless their order, on the other side.

The values can be sorted, but do not need to. The following example is then a valid one:

$$ \left[ \begin{array}{cc|cc} 6 & 23 & 5 & 0 \\ 4 & 3 & 7 & 5 \\ 23 & 4 & 2 & 7 \\ 3 & 6 & 0 & 2 \end{array} \right]; $$

but the next one is invalid because there is no bijection:

$$ \left[ \begin{array}{cc|cc} 6 & 23 & 5 & 0 \\ 4 & 3 & 7 & 5 \\ 4 & 2 & 7 & 23 \\ 3 & 6 & 0 & 2 \end{array} \right]. $$

My question is: Do you know a way to solve this problem without a brute-force approach (totally inefficient for large arrays)?

A Connection With Graph Theory?


Thanks to a link provided by EvilTeach, I am trying to make connections between this problem and graph theory. I am not an expert in this field, but I think I may have “discovered” a little something.

In order to transform my array into a graph, I take each different value and make directional links between them.

For example: if the first row is 6 23 5 0, I create a link (inside columns A and B) between 6 and 23 with an arrow to show the direction from 6 to 23. Then, I draw another link between 5 and 0 (inside columns C and D, then), with an arrow.

At the end, I count the number of times each value is designated by an arrow (“IN”) and also the number of times this same value designates another value (“OUT”).

The graph is then:

Valid array

With a valid array, we can see that the number of INs equals the number of OUTs for each value.

What happens with an invalid array?

Something like that:

Invalid array

Here, for some values, the number of IN is not equal to the number of OUT.

So let's see if there are any links between these values (here: 2, 4, 7, and 23).

  • Between 2 and 4: the link created thanks to row 3
  • Between 2 and 7: none
  • Between 2 and 23: none
  • Between 4 and 7: none
  • Between 4 and 23: none
  • Between 7 and 23: only one: row 3

Then, in this example, the graph seems to indicate that there is a problem with row 3. And this is indeed the case.

So... This approach can be seen as very naive. Indeed, some values will have self-recursive links, some will have more than 1 IN and 1 OUT, and it becomes more complex with a lot of values and links. Moreover, I do not prove anything here. Maybe it is just a lot of chance. But perhaps it is a clue of a deep connection between this problem and graph theory.

As I said earlier in this message, I am not familiar with graph theory, so you are welcome to give your remarks!

A More Complex Example


I have decided to see what happens with a more complex array:

$$ \left[ \begin{array}{cc|cc} 6 & 3 & 4 & 1 \\ 8 & 8 & 3 & 2 \\ 5 & 2 & 1 & 5 \\ 8 & 5 & 7 & 12 \\ 7 & 11 & 2 & 7 \\ 3 & 12 & 5 & 1 \\ 8 & 2 & 13 & 4 \\ 2 & 6 & 4 & 4 \\ 3 & 8 & 7 & 3 \\ 20 & 3 & 2 & 13 \\ 6 & 6 & 4 & 4 \\ 2 & 6 & 1 & 2 \\ 11 & 7 & 12 & 7 \\ 4 & 8 & 3 & 8 \\ 6 & 20 & 7 & 7 \\ 12 & 4 & 8 & 3 \end{array} \right]. $$

This array is valid: the bijections in columns A and B, and C and D, respectively, are perfect.

I have tried to create an intelligible graph which confirms the validity of the bijections (blue lines: links between A and B; orange lines: links between C and D):

Graph 2: valid array

Now, let's experiment two shifts negating the bijections, and affecting rows 7 and 12:

$$ \left[ \begin{array}{cc|cc} 6 & 3 & 4 & 1 \\ 8 & 8 & 3 & 2 \\ 5 & 2 & 1 & 5 \\ 8 & 5 & 7 & 12 \\ 7 & 11 & 2 & 7 \\ 3 & 12 & 5 & 1 \\ 13 & 4 & 2 & 8 \\ 2 & 6 & 4 & 4 \\ 3 & 8 & 7 & 3 \\ 20 & 3 & 2 & 13 \\ 6 & 6 & 4 & 4 \\ 6 & 1 & 2 & 2 \\ 11 & 7 & 12 & 7 \\ 4 & 8 & 3 & 8 \\ 6 & 20 & 7 & 7 \\ 12 & 4 & 8 & 3 \end{array} \right], $$

and its corresponding graph (purple for the new links between A and B; green for C and D):

Invalid array 2

At first glance, the errors revealed by the imbalance between the INs and the OUTs are not very efficient: the inequality concerns the integers 1, 2 and 6 linked between them such as:

  • Link between 1 and 2: none,
  • Link between 1 and 6: row 12 [great!],
  • Link between 2 and 6: row 8 [so close...].

The present “method” is half full. One the one hand, it seems to allow to detect which rows are likely to be displaced, “out of sync” with the ideal of bijection (and then, how correct them); on the other hand, it really needs to be improved in order to, perhaps, implement an algorithm allowing to solve this problem. That is why I need your help.

$\endgroup$
20
  • $\begingroup$ Is there a limit to the range of numbers that can appear in the array? $\endgroup$
    – EvilTeach
    Jun 30, 2014 at 16:25
  • $\begingroup$ What is Large N in your case? $\endgroup$
    – EvilTeach
    Jun 30, 2014 at 16:26
  • $\begingroup$ The range of numbers: 0 to 30. The size of the array in my case: 4 columns, 500 rows. $\endgroup$
    – user160928
    Jun 30, 2014 at 16:29
  • $\begingroup$ Ok. I have a different way to think about the problem. $\endgroup$
    – EvilTeach
    Jun 30, 2014 at 16:30
  • $\begingroup$ I would love to read it. $\endgroup$
    – user160928
    Jun 30, 2014 at 16:37

4 Answers 4

1
$\begingroup$

Have you considered an integer programming approach? This is not my area of expertise, so I don't know whether an array of $500$ rows will be feasible, but here's the idea.

Let there be $R$ distinct rows in the array. For $1\le r\le R,$ let $n_r$ be the number of times row $r$ occurs in the array. Since rows get cyclically permuted anyway, we may first cyclically permute each row so that it is in lexicographically minimal. This may reduce $R,$ which will result in a system with fewer variables. On the other hand, I imagine that $n_r$ will equal $1$ most of the time, so this step is not essential.

For each $1\le r\le R,$ introduce four variables, $a_{r0},$ $a_{r1},$ $a_{r2},$ $a_{r3},$ satisfying $$a_{r0}+a_{r1}+a_{r2}+a_{r3}=n_r,\qquad a_{r0}\ge0,\quad a_{r1}\ge0,\quad a_{r2}\ge0,\quad a_{r3}\ge0.\quad$$ Each of the variables $a_{ri}$ is a nonnegative integer indicating how many times the $i$-rotated version of row $r$ occurs in the final array. If $n_r=1,$ then three of the $a_{ri}$ will be $0$ and one of them will equal $1$ in any solution.

For each distinct integer, $\ell,$ that occurs in the array, we get two equations, one of which says that the number of appearances of $\ell$ in column $0$ equals the number of appearances of $\ell$ in column $1,$ the other of which says that the number of appearances of $\ell$ in column $2$ equals the number of appearances of $\ell$ in column $3.$

We then apply an integer programming method to the solution of the resulting system.

Here's an example. Start with the array $$ \begin{bmatrix} 0 & 6 & 23 & 5\\ 3 & 7 & 5 & 4\\ 2 & 7 & 23 & 4\\ 0 & 2 & 3 & 6 \end{bmatrix}, $$ which has lexicographically minimal rows, obtained from one of your examples. Let $a_{10}$ be the number of times $(0,6,23,5)$ appears in the final array, $a_{11}$ the number of times $(5,0,6,23)$ appears in the final array, $a_{12}$ the number of times $(23,5,0,6)$ appears in the final array, $a_{13}$ the number of times $(6,23,5,0)$ appears in the final array, $a_{20}$ the number of times $(3,7,5,4)$ appears in the final array, $a_{21}$ the number of times $(4,3,7,5)$ appears in the final array, and so on.

The number of times $0$ appears in column $0$ of the final array is $a_{10}+a_{40};$ the number of times it appears in column $1$ of the final array is $a_{11}+a_{41}.$ This yields the equation $$ a_{10}+a_{40}=a_{11}+a_{41}. $$ Similarly, the number of times $0$ appears in column $2$ of the final array is $a_{12}+a_{42};$ the number of times it appears in column $3$ of the final array is $a_{13}+a_{43}.$ This yields the equation $$ a_{12}+a_{42}=a_{13}+a_{43}. $$

For the element $2,$ we get the equations $$ \begin{aligned} a_{30}+a_{43}&=a_{31}+a_{40}\\ a_{32}+a_{41}&=a_{33}+a_{42}. \end{aligned} $$ We get similar pairs of equations for the elements $3,$ $4,$ $5,$ $6,$ $7,$ and $23.$

Our final system consists of all of the above equations, combined with $$ \begin{aligned} a_{10}+a_{11}+a_{12}+a_{13}&=1\\ a_{20}+a_{21}+a_{22}+a_{23}&=1\\ a_{30}+a_{31}+a_{32}+a_{33}&=1\\ a_{40}+a_{41}+a_{42}+a_{43}&=1, \end{aligned} $$ and the inequalities $a_{ri}\ge0$ for $1\le r\le4,$ $0\le i\le3.$

The idea is to feed this system into an integer programming routine, such as branch-and-cut. I don't have experience with the standard packages for doing such things, but I did try solving some systems with Mathematica, using the command "Reduce[system,Integers]". Playing around a bit, I managed to get Mathematica to solve systems up to $35$ rows, and I'm sure it could go higher. I have no idea what's going on internally, and whether it's state-of-the-art or not. It definitely looks likes it's scaling far better than brute force does. It might be worth trying more specialized software.

I've added some tags to your post to see whether we can get some experts to weigh in.

Added: The array above has the property that every distinct array element occurs exactly twice and in exactly two different rows, which is atypical. Here's a better example, which shows that the constraints can look more complicated than they do in the previous example. Consider the array $$ \begin{bmatrix} 1 & 1 & 6 & 5\\ 1 & 3 & 5 & 6\\ 1 & 6 & 6 & 2\\ 1 & 1 & 2 & 3 \end{bmatrix}. $$ The constraint that the element $1$ occur the same number of times in columns $0$ and $1$ is $$ a_{10}+a_{13}+a_{20}+a_{30}+a_{40}+a_{43}=a_{11}+a_{10}+a_{21}+a_{31}+a_{41}+a_{40}. $$ The constraint that the element $1$ occur the same number of times in columns $2$ and $3$ is $$ a_{12}+a_{11}+a_{22}+a_{32}+a_{42}+a_{41}=a_{13}+a_{12}+a_{23}+a_{33}+a_{43}+a_{42}. $$ The constraint that the element $6$ occur the same number of times in columns $0$ and $1$ is $$ a_{12}+a_{21}+a_{33}+a_{32}=a_{13}+a_{22}+a_{30}+a_{33}. $$ The constraint that the element $6$ occur the same number of times in columns $2$ and $3$ is $$ a_{10}+a_{23}+a_{31}+a_{30}=a_{11}+a_{20}+a_{32}+a_{31}. $$

Also, about $40$ rows appears to be practical limit of what the Mathematica Reduce command can handle, at least on my laptop.

$\endgroup$
11
  • $\begingroup$ Interesting solution. Thanks for it (and for the tags!). If I understand it, the program needs to compute 500x4 values + 2000 variables (4 per row) + 1 equation per row (a_r0 + a_r1 + a_r2 + a_r3 = 1) (then 500 equations per array) + 1 equation for the different values * the number of times they appear in a different row (let's say 30 different values present in 50 different rows: about 1500 equations). 4000 variables + 2000 equations. Is that correct? If so, I guess it is still too huge, even with a brute-force/branch-and-cut type algorithm. $\endgroup$
    – user160928
    Jul 2, 2014 at 0:47
  • $\begingroup$ It would be $4\times500=2000$ variables, along with $2000$ nonnegativity constraints, $x_{ri}\ge0.$ Then there is one equation per row plus two equations per distinct array element. So $500+2\times31=562$ equations. Perhaps a further example will clarify what the equations for the distinct array elements look like. I'll add one. I agree that this is a big system, but I'm unsure where the limit of solvability is. $\endgroup$ Jul 2, 2014 at 4:42
  • $\begingroup$ Thanks for the clarification. For my part, I'm working on the graph theory approach and will try to edit my post in a few hours. $\endgroup$
    – user160928
    Jul 2, 2014 at 4:58
  • $\begingroup$ “about 40 rows appears to be practical limit of what the Mathematica Reduce command can handle, at least on my laptop.” Could you please tell me how you use the Reduce command in this context? Thanks! $\endgroup$
    – user160928
    Jul 2, 2014 at 16:17
  • $\begingroup$ You need to create a system of equations/inequalities. Here's an example for the array $$ \begin{bmatrix} 1 & 1 & 2 & 3\\ 1 & 1 & 3 & 2 \end{bmatrix}. $$ system=(a[1,0]+a[1,1]+a[1,2]+a[1,3]==1 && a[2,0]+a[2,1]+a[2,2]+a[2,3]==1 && a[1,0]>=0 && a[1,1]>=0 && a[1,2]>=0 && a[1,3]>=0 && a[2,0]>=0 && a[2,1]>=0 && a[2,2]>=0 && a[2,3]>=0 && a[1,0]+a[1,3]+a[2,0]+a[2,3]==a[1,1]+a[1,0]+a[2,1]+a[2,0] && a[1,2]+a[1,1]+a[2,2]+a[2,1]==a[1,3]+a[1,2]+a[2,3]+a[2,2] && a[1,2]+a[2,1]==a[1,3]+a[2,2] && a[1,0]+a[2,3]==a[1,1]+a[2,0] && a[1,1]+a[2,2]==a[1,2]+a[2,1] && a[1,3]+a[2,0]==a[1,0]+a[2,1]) $\endgroup$ Jul 2, 2014 at 16:38
0
$\begingroup$

In the context of the 4X4 example. Call this array A. I would create an array of 4 X 31, and initialize them to zero. Call this array C. The value 4 is the number of rows within the array.

For each row, i would iterate though its columns and increment the element in C which is subscripted by the value in A. This would yield C row 1 as [0][2][0][0][0][0][2][0]... There are two 1s and two 7s.

C looks like this

  • [0][2][0][0][0][0][0][2]...
  • [0][2][0][0][2][0][0][0]...
  • [0][2][0][0][0][2][0][0]...
  • [0][0][0][2][0][2][0][0]...

Scan the columns looking left to right. You need a column value for each row that is at least 2.

Some possible solutions include. 1,1,1,3 1,4,1,3 1,4,5,5

Now you probably have a smaller list of possible solutions.

do some O(N) type looping shifting stuff into place until you verify that the solution is correct or impossible.

$\endgroup$
7
  • 1
    $\begingroup$ The validity of this answer depends on the answer to the question I asked above. As the question is posed the answer would be 'yes', which makes your solution invalid. There need not be a single number that occurs more than once in any row. $\endgroup$ Jun 30, 2014 at 16:55
  • $\begingroup$ Here's a MathJax tutorial :) $\endgroup$
    – Shaun
    Jun 30, 2014 at 17:04
  • $\begingroup$ Very interesting solution. Thanks! For some reasons, it makes me thinks to the Knuth's dancing links, I don't know why. I have edited my post in order to add another example of a valid result. Please tell me if it seems to you that your solution still works. $\endgroup$
    – user160928
    Jun 30, 2014 at 17:09
  • $\begingroup$ No. I didn't understand your problem. I think your goal is to determine if it is possible to perform shifts on 0 or more rows, to partition the array into pairs of columns where each column contains the same set of numbers, but not necessairly in the same order. $\endgroup$
    – EvilTeach
    Jun 30, 2014 at 19:41
  • $\begingroup$ The stumbling block here is that you need to have all the rows in place to test whether or not it is valid. Performing 4 shifts on each of the 500 rows, one at a time, and testing is an large number of computations. $\endgroup$
    – EvilTeach
    Jun 30, 2014 at 23:19
0
$\begingroup$

Assuming that one is using the brute force algorithm, there may be a way to make the "test if this is valid solution" run faster.

For the discussion assume we have a 500 row by 4 array which holds the integer values to test. Those integers range from 0 .. 30. We have two groups of related columns (A, B) and (C, D).

Ignoring (C, D) we can compute two values.

  1. Sum(A)
  2. Sum(B)

If those two sums differ, then we do not have a valid solution.

We can compute two other values (adding 1, so that zero is not part of the product)

  1. Product(A + 1)
  2. Product(B + 1)

If those two products differ, then we do not have a valid solution.

If we have a valid solution, print it and stop otherwise, do the next brute force shift, and retest. Continue that process until a solution is found, or we run out of shifts.

Now to speed it up, consider this:

  • At any time, we know the two sums, and the two products.
  • When we go to do a shift, we can adjust the sums and the products to remove the values for that row.
  • After the shift we can adjust the sums and the products to add the "new" values for that row.

Other factors

  • N is still very large
  • the product can get large 31^500 probably won't fit in an int32. Hell maybe not an int64
$\endgroup$
4
  • $\begingroup$ Good idea. We can also make a copy of the array, sort all the values by column A and B, and then compare each row. If value [A,n] equals value [B,n], we continue with n+1, n+2, and so on. And then, if everything is ok, we compute the values in C and D. The problem is that it is not really efficient. I have tried this solution and had no results for 500 rows with 30 different values. But perhaps I am not a good programmer, ah ah. $\endgroup$
    – user160928
    Jun 30, 2014 at 23:45
  • $\begingroup$ This way, you don't need to copy or sort the array. Just run through all of the shifts. $\endgroup$
    – EvilTeach
    Jun 30, 2014 at 23:47
  • $\begingroup$ Even in this case, N is extremely large. I'm not optimistic with a brute-force solution. $\endgroup$
    – user160928
    Jun 30, 2014 at 23:49
  • $\begingroup$ Yep. I just tested an Int64. 31^500 is way too large for it. Some lateral thinking is needed. I'm coming up dry. $\endgroup$
    – EvilTeach
    Jun 30, 2014 at 23:54
0
$\begingroup$

A quick update.

I have solved this problem using a genetic algorithm I wrote in C++. It is able to find a solution in 1 or 2 hour(s). It is not even optimized (I am new to C++; my program is not even parallelized).

Initialization: DNA: encodage of the shift (for each line: 0 to 3, 0 for no shift, 3 for max shift to the right).

E.g. :

0: { 1 2 3 4 }
1: { 4 1 2 3 }
2: { 3 4 1 2 }
3: { 2 3 4 1 }

Evaluation: std::set_intersection for the number of bijections; fitness = 1/(# bijections max-#bijections in the DNA+1); if fitness = 1, break (we have a solution).

Selection: a simple 50|50 one-point crossover.

Mutation: 1%

GA gives amazing results for this NP-complete problem.

If you want more information, feel free to contact me.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy