Заполните двумерный массив через индекс по ближайшему диапазону

Question

Трудно описать, чего я хочу, поэтому начну с примера:

Index   ArrayPos
1       0,0
2       1,0
3       0,1
4       1,1
5       2,0
6       2,1
7       2,2
8       0,2
9       1,2
10      1,2
11      3,0
12      3,1

и так далее. В основном я хочу заполнить массив не строка за строкой или столбец за столбцом, но всегда ближе всего свободное место до 0,0.

Было бы здорово, если бы длительность алгоритма всегда была одинаковой независимо от того, будет ли я хотеть получить позицию массива для индекса 3 или 4237882348.

Я попробовал кое-что с модулем, но так и не получил.

Answer 1

Если вас не волнует порядок x, y и y, x, то это должно работать для вас:

let x = ceiling(sqrt(Index)) - 1
let y = ceiling((Index - x^2)/2) - 1
if Index is odd, swap x and y

При этом, хотя 4,4 предшествует 5,0,так что это зависит от того, какой порядок вы хотите получить, увеличивая числа, которых у вас нет в вашем примере ...

Answer 2

Если алгоритм может запомнить последнюю позицию, это будет довольно просто.

Вы начинаете с числа rank , равного 0. Для каждого ранга r имеется 2r+1 свободных позиций. Таким образом, r = 0 => одна доступная позиция, которая составляет 0,0, Для каждого ранга вы генерируете 2r+1 позиций и сохраняете их в массиве. Значения генерируются

для каждого r, цикл и начало создания позиций r,0 - 0,r - r,1 - 1, r ... до r,r Таким образом, с каждым новым индексом используйте одну из созданных позиций, пока не будет свободной позиции. Затем увеличивайте ранг и продолжайте.

Неясно, какое измерение расстояния имеет в виду, но это работает в соответствии с примером.

Answer 3

Если мы возьмем p-норму, где p = бесконечность (она же максимальная норма), которая определяет расстояние как максимальную координату, что выглядит как ваш пример, то следующее работает в javascript (хотя логика работает в любомназовите, пожалуйста):

var i=1, L=0, n=15, x,y;
outer: while (true) {

  for (var j=1; j<=2*L+1; j++) {
    x = j<=L ? L : 2*L+1 - j;
    y = j<=L ? j-1 : L;
    document.write(x+" "+y+"<br/>");
    i++;
    if (i>n) {
      break outer;
    }
  }
  L++;
}

Обратите внимание, что n - это количество элементов, которые вы хотите напечатать, и вы можете изменить строку document.write, чтобы сделать с ней все, что вы хотите.Поэтому, если вы хотите заполнить свой 2d массив значениями из одного массива:

n = oneDimArray.length;

И вместо document.write:

newArray[x][y] = oneDimArray[i];