Отображение числа в N-мерную сетку / массив - PullRequest
Новая
       10

Отображение числа в N-мерную сетку / массив

0 голосов
/ 23 декабря 2010

Предположим, например, что у меня есть трехмерная сетка / массив, где ось проходит от 1 до 1000 (или от 0 до 999 соответственно).Этот массив имеет 1000 ^ 3 элементов.

Я хотел бы отобразить одно целое число в диапазоне от 0 до 1000 ^ 3 в этот массив детерминистическим способом с использованием Java.Предпочтительно, чтобы это решение работало для любого измерения N.

Вот псевдокодийный пример такой функции: 

public Vector<int> nthElement( Vector<int> dims, int n )

Так что, если бы я назвал его как nthElement([1000, 1000, 1000], 0), он вернул бы[0, 0, 0], тогда как nthElement([1000, 1000, 1000], 1001) вернет что-то вроде [999, 1, 0].

Решение должно быть для N измерений, а не для 3, как в моем примере.

Ответы [ 4 ]

3 голосов
/ 23 декабря 2010

Это правильный алгоритм отображения: 

map([X, Y, Z, T, ...], N) = [
    N mod X, 
    N div X mod Y, 
    N div X div Y mod Z, 
    N div X div Y div Z (mod ...)?
    ...
]

или рекурсивный 

map([X, Y, Z, T, ...], N) = [N mod X, map([Y, Z, T, ...], N div X)]

Где A div B - это этаж (A / B).

1 голос
/ 23 декабря 2010

отметьте это 

List<Integer> nthElement( List<Integer> dims, int n ){
    List<Integer> res = new ArrayList<Integer>(dims.size());
    for(Integer cur  : dims){
        if(n <= 0 ){
            res.add(0);
        } else {
            n -= cur;
            res.add(n >= 0 ? cur -1  : cur + n );
        }
    }
    return res;
}

обн примеры использования 

    //create list with 3 dimensions using Guava
    List<Integer> dims = ImmutableList.of(1000, 1000, 1000);
    //or with standard JDK
    //List<Integer> dims = new ArrayList<Integer>(3);dims.add(1000);dims.add(1000);dims.add(1000);

    System.out.println(nthElement(dims, 0));
    System.out.println(nthElement(dims, 1000));
    System.out.println(nthElement(dims, 1001));
    System.out.println(nthElement(dims, 2001));

напечатает 

    [0, 0, 0]
    [999, 0, 0]
    [999, 1, 0]
    [999, 999, 1]
1 голос
/ 23 декабря 2010

Вы можете сделать: 

a = Number % (1000 * 1000)
b = (Number / 1000) % 1000
c = Number / (1000 * 1000)

Это отображение (уникальное), и вы можете просто сделать обратное

примечание 2/3 = 0 не .6666

0 голосов
/ 23 декабря 2010

Вероятно, вы ищете функцию сопряжения Кантора . Он определен для NxN, поэтому вы можете использовать его для сколь угодно больших размеров. Как упоминалось на странице википедии, оно может быть индуктивно обобщено на массив измерения n, в вашем случае n = 3 работает просто отлично.

На приведенной выше странице также объясняется инвертирование функции, поэтому вы можете получить свои координаты в массиве по заданному номеру, что в точности соответствует желаемому с nthElement.

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

Edit: Я должен отметить, что если ваш массив имеет прямоугольные размеры, функция спаривания Кантора будет принимать размеры самого большого вида. Таким образом, связанные числа больше не находятся в вашем массиве. F.ex. массив размером 1000x2 будет рассматриваться как массив 1000x1000, а числа, соответствующие записям в вашем фактическом массиве, будут представлять собой непоследовательный список чисел 0..1000 * 1000. Однако, если ваши три измерения всегда одинаковы, то этот момент можно полностью игнорировать.

В ответ на комментарий: Row-by-row и Cantor - это просто разные способы пройти через пространство матрицы. Преимущество спаривания Кантора состоит в том, что оно определяется над натуральными числами и, следовательно, также применимо, если у вас нет точных значений для ваших размеров матрицы, или ваша матрица со временем увеличивается.

...