Квадратная матрица перестановка

Question

У меня есть набор предметов размером N. Предметы отсортированы по вероятности.Квадратная матрица m [N] [N] этих элементов в организации памяти в стиле C будет иметь элементы с одинаковыми вероятностями.Например, m [0] [100] будет очень далеко от m [100] [0] и всех остальных с аналогичной вероятностью.Мне нужно переставить элементы простым способом, чтобы более вероятные были ближе к 0. Это не обязательно должна быть квадратная матрица, это может быть вектор [N * N].И это не обязательно должно быть идеально, просто достаточно хорошо, чтобы элементы с одинаковой вероятностью были несколько сгруппированы вместе.

Я ищу функцию f (i, j) для определения положения в переставленной матрице/вектор.Если возможно с очень простыми операциями (например, без квадратов и делений, но с програматическими условиями все в порядке)

Для более графической ссылки, я ищу что-то вроде этого.[Из «Истории математики» Би-би-си по аргументу Кантора]

Но это не обязательно должна быть именно эта перестановка.Просто то, что элементы, идущие по диагонали, в основном сгруппированы поблизости.

Ну, я знаю, что это, вероятно, что-то очень простое, но прошло много лет с тех пор, как школа / университет и Вольфрамальфа не помогают.* Спасибо!

Answer 1

Ваш вопрос немного неясен, но на графике вам нужна функция, которая описывает отображение этого пути, например f (1,2) = 8.

i + j дает индекс диагонали, назовите его d. В диагонали над ней имеется (d + 1) d / 2 элементов. Если d четное, мы считаем вверх и вправо, если это нечетное, мы считаем вниз и влево, поэтому число элементов, которые мы посчитали по диагонали, равно j + 1 или i + 1 соответственно: 1003 *

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:
Я чувствую себя дураком. Функция выше работает для 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);
}