将数字映射到 N 维网格/数组

Question

例如，假设我有一个 3 维网格/数组，其中轴从 1 到 1000（或等效的 0 到 999）。该数组有 1000^3 个元素。

我想使用 Java 以确定的方式将 0 到 1000^3 范围内的单个整数映射到该数组。优选地，该解决方案适用于任何维度 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 维。

Answer 1

这是正确的映射算法：

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 是 Fl​​oor(A/B)。

Answer 2

检查这个

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]

Answer 3

你可以这样做：

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

这是一个映射（唯一），你可以简单地做反向

注释 2/3 = 0 而不是 .6666

Answer 4

您可能正在寻找Cantor 配对函数。它是为 NxN 定义的，因此您可以将其用于任意大的尺寸。正如维基百科页面上提到的，它可以归纳推广到维度为 n 的数组，在您的情况下 n=3 工作得很好。

上面的页面还解释了函数的反转，这样您就可以从给定的数字获取数组中的坐标，这正是您想要的 nthElement 。

当然，康托只定义了一种穿过二维场的可能方法。还有其他可能的步行方式，但这是最受欢迎的方式。

编辑：我应该提到，如果你的数组具有矩形尺寸，康托配对函数将假定最大类型的尺寸。因此关联的数字不再连续出现在数组中。 F. 前。大小为 1000x2 的数组将被视为 1000x1000 数组，并且与实际数组中的条目对应的数字将只是数字 0..1000*1000 的非连续列表。
然而，如果你的三个维度始终相同，那么这一点可以完全忽略。

回应评论：逐行配对和康托配对只是遍历矩阵空间的不同方式。康托配对的一个优点是它是在自然数上定义的，因此如果您没有矩阵维度的精确值，或者您的矩阵随着时间的推移而增长，它也适用。