wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Sorting a Matrix
        
(Message started by: Barukh on Apr 9^th, 2013, 11:32pm)

Title: Sorting a Matrix
Post by Barukh on Apr 9^th, 2013, 11:32pm

A matrix MxN contains a permutation of numbers 1, 2, ..., MN.

You are allowed to perform a sequence of the following transformations of the matrix: choose any 2x2 sub-matrix, and rotate the content of the cells clockwise by 90 degrees.

What are the necessary and sufficient conditions of the matrix in order to be able to transform it to a natural sorted row-major order (the first row contains numbers 1, ..., N; the second - N+1, ..., 2N; etc.)

Source: Inspired by Croatian On-line Olympiad in Informatics (past).

[hide]I don't know the answer.[/hide]

Title: Re: Sorting a Matrix
Post by Grimbal on Apr 10^th, 2013, 6:43am

I would say
[hide]
It is possible if
- M=0 or N=0
- M=1 or N=1 and the array is already sorted
- M=2 and N=2 and the array is a rotation of the sorted array
- all sizes larger than 2x2
[/hide]

PS: not sure about 2x3, though.

Title: Re: Sorting a Matrix
Post by SMQ on Apr 11^th, 2013, 8:16am

on 04/10/13 at 06:43:27, Grimbal wrote:

PS: not sure about 2x3, though.

2x3 is not possible; only 120 of the possible 720 permutations are solvable. I'm working on classifying them now. [hide]All larger sizes are indeed solvable.[/hide]

--SMQ

Title: Re: Sorting a Matrix
Post by Grimbal on Apr 11^th, 2013, 8:34am

Yep. In the meantime I did a computer search and found the same result.

But I haven't found a simple rule that tells whether a position is possible or not.

Now that I think of it, [hide]the 120 out of 720 would suggest a formula that must equal 0 (mod 6).[/hide]

Title: Re: Sorting a Matrix
Post by SMQ on Apr 11^th, 2013, 9:07am

on 04/11/13 at 08:34:21, Grimbal wrote:

Now that I think of it, [hide]the 120 out of 720 would suggest a formula that must equal 0 (mod 6).[/hide]

In fact, [hide]looking at just one of the rows (of three elements), all 120 possible arrangements of that row occur in the set of solvable permutations--each paired with a unique arrangement of the other row.[/hide]

--SMQ

Title: Re: Sorting a Matrix
Post by Grimbal on Apr 12^th, 2013, 4:14pm

Nice find. I printed out the solutions in order, but I didn't notice that pattern.

Looking further into it, it seems [hide]you can choose the value of any 3 cells, it leaves exactly one valid possibility for the 3 remaining cells[/hide].

It is a set of permutations where [hide]2 permutations differ by at least 4 values[/hide].

Title: Re: Sorting a Matrix
Post by Barukh on Apr 13^th, 2013, 10:59am

on 04/11/13 at 08:16:21, SMQ wrote:

[hide]All larger sizes are indeed solvable.[/hide]

--SMQ

Got a proof?

The 2x3 case suggests the following formulation in terms of group theory: Given a permutation group of 6 elements (formally: symmetric group S₆), and 2 elements of the group a = (1 2 3 4), b = (3 4 5 6), what is the size and structure of the subgroup, generated by these 2 elements?

Note that for the 2x4 case we add another element c = (5 6 7 8), and then 3 elements a, b, c generate the whole group S₈. What is the fundamental difference between these two cases? I am pretty sure that group theory methods have answers to these questions… Trying to figure out.

Title: Re: Sorting a Matrix
Post by Grimbal on Apr 13^th, 2013, 1:42pm

There is no fundamental difference, except that you have more freedom, now enough to build every permutation.

You have to think like with a Rubik's cube:

Let's see for the 2x4 matrix
1 2 3 4
5 6 7 8
and name the operations (numbers refer to cells, not value transformations):
A = 1->2->6->5->1
B = 2->3->7->6->2
C = 3->4->8->7->3
and
A' = A³ (=A^-1)
B' = B³
C' = C³

You can see that the operations (apply from left to right)
C'BAB'CBA'BB
tansform the matrix to
1 6 3 4
5 2 7 8

You can see that 6 and 2 are switched. By composition you can switch any 2 cells. And from there you can build every permutation.

A similar construct works for the 9x9 matrix.

Title: Re: Sorting a Matrix
Post by SMQ on Apr 13^th, 2013, 2:14pm

on 04/13/13 at 10:59:10, Barukh wrote:

Got a proof?

I have a constructive "proof", even. ;)

For 2xN (N >= 4), given 2x4: work from one end to the other until only a 2x4 segment remains, then solve it. Since any 2x4 segment can be placed in any arbitrary configuration it is always possible to move the last two unsolved numbers into position.

For 3x3, given two diagonally overlapping 2x2 squares can be placed in any arbitrary configuration: first solve two opposite corners, then solve the remaining 7 cells using the given.

For MxN (M, N >= 3), given 3x3: work toward one corner, solving one edge of the unsolved rectangle until only a 3x3 region remains, then solve it. Since any 3x3 segment can be placed in any arbitrary configuration, it's always possible to move all the numbers along an edge of length >= 3 into position.

--SMQ