Given a list of n numbers (drawn in blue), any pair of numbers gives rise to a new number, namely the difference.
All these differences can logically be arranged in a matrix (drawn here in black): In position (i, j), with i, j running from 0 to n-1, the difference between the i'th and the j'th number is written.
Pressing the BLACK entry (i, j) in the matrix will swap the numbers i and j in the (blue) list. This will cause changes in the matrix in rows and columns i and j.
Arrange the list such that the numbers in the matrix are sorted; i.e., such that there is *some* systematic way of traversing the matrix that reaches all numbers in increasing order. E.g., it could be going along diagonals, line by line, column by column, or some other clever (systematic!) path.
- if you can do this, you have solved the problem I talked about at our journal club on Oct. 9th: then we have a query time of O(log n) for finding a peptide mass in a proteine while still using only O(n) space (since there is no reason to actually save the whole matrix if you can find the entries in a fast systematic way). And you'll be co-authoring a paper for the next WABI conference (which is in Budapest..).
When you press the mousebutton on a number, the numbers in the list that will be swapped are circled and numbers in the matrix that will be affected by this swap turn red. Releasing the button causes the swap. If you regret, press the same number again.