Programming Theory: Shuffling a 2D Array [closed]

Tag: arrays , complexity-theory , theory , shuffle , computation-theory Author: LIUYUWENHOME Date: 2012-08-25

Me and a friend are mulling over an interesting Computer Science question.


You have a simple 2D Array:

[  1,  2,  3,  4 ]
[  5,  6,  7,  8 ]
[  9, 10, 11, 12 ]
[ 13, 14, 15, 16 ]

Now take this array and shuffle all the elements in the array:

[ 11,  5, 14, 10 ]
[  8,  2,  4, 16 ]
[ 15,  1,  3, 13 ]
[  6, 12,  9,  7 ]

A fairly simple concept at first. However, what if we take it one more step? Now, shuffle the original array such that no elements of the new array are next to an item they were adjacent to in the original array in a cardinal direction.

Our first shuffle fails as 1 is next to 2 and was also next to 2 in the original array.

Here is a working example:

[  7, 16, 13,  2 ]
[ 14,  3,  5,  8 ]
[  9,  1,  4, 11 ]
[ 12, 10, 15,  6 ]

Still not too bad. Now to the real question!

Shuffle the original array again such that no elements of the array are next to an element they were adjacent to in either cardinal directions or via diagonals.

Our working example fails since 1 is next to 5 diagonally and was next to 5 in the original array.

Some Thoughts:

  1. Can an array even be determined?
  2. Does it depend on the size of the array?
  3. Does the array need to be symmetrical?
  4. Does the array need to have an even / odd amount of elements?
  5. Does a solution hold for all arrays of size M by N?
  6. If there exists a solution, what would be the running time to find the new array?

What do you think?

EDIT

I am surprised to find my question closed as "off topic". According to the FAQ if my question "...generally covers a specific programming problem..." then it is allowed to be asked and is not "off-topic".

The bottom-line question I was asking is:

"Can you take a 2D array and shuffle it so no members will be next to each other in the new array, including diagonals".

Is that not a good programming question? I feel strongly my question should not be closed.

Answer to #2 is clearly yes. A 2x2 array has no solution.
A 3x3 array has no solution either, since the middle number is originally adjacent to all other numbers.
A simple 90 degree rotate will probably do what you want. Elements will not be adjacent horizontally with regards to the original, not will they be diagonal. If the array is still read in the original manner, it is effectively shuffled.
This breaks my brain a little. I'm gonna puzzle over it for a while. I take it that the adjacency rules do not wrap around the left/right and top/bottom, given the (2,6) pair as an example.
The minimum size is 4x4. My answer will only work if you are applying this to a real world situation. If you are looking for a "shuffled to the eye" solution, this is much more complex.

Other Answer1

1.Can an array even be determined?
  • Sure, you can use a transformation Rn -> RN via transposing to edges.

2.Does it depend on the size of the array?

  • You can't do it for MxM <= 3, so Yes.

3.Does the array need to be symmetrical?

  • It depends *

Does the array need to have an even / odd amount of elements?

  • It depends *

5.Does a solution hold for all arrays of size M by N?

  • It depends *

6.If there exists a solution, what would be the running time to find the new array?

Running time could be O(N^2) using a simple transformation (considering though as O(1)).

  • This depends on considering duplicates as part of the solution (a bag) or not (a set).

Now as for the algorithm itself. Although this seems like a nice way to brain exercise it sounds more like a homework so why don't you try something and ask for specifics.