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

Question

Imagine this Table:

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.

Answer 1

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).