Sorting Algorithm which prevents strings with at least one identical char from being next to each other Imagine this Table:



All combinations represented in the table (1,2 ; 1,3 ; 1,4 ; etc.) are stored as strings in an array with a total of  (n^2-n)/2  elements (combinations).

I'm looking for an algorithm that sorts the elements so no number of a combination is next to a combination with the same number in it. 

For example a sorted array with n=5: {1,2 ; 3,4 ; 5,1 ; 2,3 ; 5,4 ; 1,3 ; 2,5 ; 4,1 ; 3,5 ; 4,2}

Of course this algorithm would only work with n > 4.
Think of this like a chess board.  Visit all of the white squares first (in a left-to-right, top-to-bottom scan).  Then visit all of the black squares (in a similar order).