c - 方阵置换

Question

我有一组大小为 N 的项目。这些项目按概率排序。这些项目的方阵 m[N][N]，在 C 风格的内存组织中，将具有相似概率的元素展开。例如，m[0][100] 将与 m[100][0] 和所有其他具有相似概率的人相去甚远。我需要以一种简单的方式排列元素，以便更可能接近 0 的元素。它不需要是方矩阵，它可以是 vector [N*N]。它不需要是完美的，只要足够好，具有相似概率的元素在某种程度上组合在一起即可。

我正在寻找一个函数 f(i,j) 来给出置换矩阵/vector 上的位置。如果可能的话，使用非常简单的操作(例如，没有平方和除法，但程序条件是可以的)

要获得更多图形引用，我正在寻找类似的东西。 [摘自 BBC 关于康托尔论点的数学故事]

但它不需要完全是那种排列。只是走在对角线上的元素大多在附近分组。

好吧，我知道这可能是一件非常简单的事情，但是学校/大学和 Wolframalpha 已经很多年没有帮助了。

谢谢!

Answer 1

你的问题有点不清楚，但是通过图形你想要一个描述该路径映射的函数，例如 f(1,2) = 8。

i+j 给出对角线的索引，称之为 d。该元素上方的对角线中有 (d+1)d/2 个元素。如果 d 是偶数，我们向右向上计数，如果为奇数，我们向左向下计数，所以我们在对角线上计数的元素数分别为 j+1 或 i+1:

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);
}

编辑:
我觉得自己像个傻瓜。上面的函数适用于 d<=N，但不适用于 d>N(矩阵的右下半部分)。

要事第一。出于某种原因，我从 1 而不是 0 开始索引，因此 f(0,0) = 1，这实际上并不一致。因此，如果您不介意，我会删除那个 +1，这样 f(0,0)=0。现在来处理右下半部分，

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);
}