Square Matrix Permutation

I have a set of items of size N. The items are sorted by probability. A square matrix m[N][N] of those items, in C style memory organization, would have elements with similar probabilities spread out. For example m[0][100] will be very far from m[100][0] and all others with similar probability. I need to permutate the elements in a simple way so the more likely ones tend to be closer to 0. It doesn't need to be a square matrix, it can be a vector [N*N]. And it doesn't need to be perfect, just good enough that elements with similar probability are somewhat grouped together.

I'm looking for a function f(i,j) to give the position on the permutated matrix/vector. If possible with ver开发者_Python百科y simple operations (e.g. no squares and division but programatic conditionals are OK)

For a more graphical reference, I'm looking for something like this. [From BBC's The Story of Maths on Cantor's argument]

But it doesn't need to be exactly that permutation. Just that the elements walked on the diagonals are mostly grouped nearby.

Well, I know this is probably something very simple but it's been many years since school/uni and Wolframalpha isn't helping.

Thanks!

Your question is a little unclear, but by the graphic you want a function that describes the mapping of that path, for example f(1,2) = 8.

i+j gives the index of the diagonal, call it d. There are (d+1)d/2 elements in the diagonals above that one. If d is even, we are counting up and to the right, if it is odd we are counting down and to the left, so the number of elements we have counted in the diagonal is j+1 or i+1, respectively:

unsigned int f(unsigned int i, unsigned int j)
{
  unsigned int d = i+j;
  unsigned int k = (d+1)*d/2 + (d%2 ? i : j) + 1;
  return(k);
}

EDIT:
I feel like a fool. The function above works for d<=N, but not d>N (the lower right half of the matrix).

First things first. For some reason I started the index at 1 instead of 0, so that f(0,0) = 1, which isn't really consistent. So if you don't mind I'll remove that +1, so that f(0,0)=0. Now to deal with the lower right half,

unsigned int f(unsigned int i, unsigned int j, unsigned int N)
{
  unsigned int d = i+j;
  if(d>=N)
    return(N*N - f(N-1-i, N-1-j, N) - 1);
  unsigned int k = (d+1)*d/2 + (d%2 ? i : j);
  return(k);
}