Sorting a two-dimensional toroidal array with rotations and swaps

Question

I tried thinking of an algorithm, but couldn't do it. Here is the problem:

There are 16 elements, grouped by four types (a, b, c and d). We also have four groups, A, B, C and D.

In the initial state, the four groups have four random elements each, eg.:

A: c, c, a, d
B: b, b, a, a
C: b, b, c, c
D: d, d, d, a

The order of elements in the group is significant.

There are two operations permitted:

1) rotating the elements of the group (in both directions), eg.:

c, c, a, d -> d, c, c, a

2) swapping two adjacent elements in a group with the corresponding elements in an adjacent group, considering that the first and last groups and elements are also adjacent, so.:

A: (c, c), a, d
B: (b, b), a, a

->

A: (b, b), a, d
B: (c, c), a, a

or

A: c), c, a, (d
D: d), d, d, (a

->

A: d), c, a, (a
D: c), d, d, (d

The goal of the algorithm is to place the elements into their corresponding groups (A: a, a, a, a, etc.). The algorithm doesn't have to be optimal in terms of time and solution, but it should be reasonably fast on average (ie. no brute-force).

Can anyone help? Is this algorithm even polynomial?

Answer 1

My initial idea would be to attempt some form of Dynamic Programming - the problem seems relatively similar to Edit Distance in that you have a limited set of operations and a known desired end state. A dynamic programming approach would yield a poly-time algorithm. But, like I say, this is just where I would start searching for an algorithm, I don't know if this approach would actually work. If I get some time later I'll have a deeper think.

Hope this helps!

Answer 2

I think it is always possible. First consider the case when a letter (say b) appears only in two rows X and Y. We can ensure that X and Y are adjacent by the swap operations.

Case i)

X: b - - -
Y: - b b b

We can make X all b's by

Cyclich shift X.

X: - - b - 
Y: - b b b

swap middle

X: - b b -
Y: - - b b

Now cyclic shift and swap.

Case ii)

X: b - b -
Y: b - b -

make it

X: - b - b
Y: b - b -

Swap last two.

The other case is trivial.

Now given any distribution of a particular letter in 2,3 or 4 rows, we can ensure that it appears only in two rows. I will leave that to you, as it is easy to see and hard to type!

(If it appears only in one row, our work is mostly done for that letter)

Thus the algorithm would be

Ensure a appears only in two rows. Make sure the rows are A and B (by swapping later).

Now perform above to make A to be aaaa.

Ignore A.

Consider B,C,D. Ensure that b appears only in two rows. Make B to be bbbb as above.

Ignore B.

Given C and D, you can use the above to make C to be cccc, D will be dddd.