0

例如，假设我有一个 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 维。

4

4 回答 4

3

这是正确的映射算法：

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）。

于 2010-12-23T12:10:30.743 回答
1

检查这个

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]
于 2010-12-23T12:22:18.360 回答
1

你可以做：

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

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

注意 2/3 = 0 不是 .6666

于 2010-12-23T12:13:33.763 回答
0

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

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

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

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

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

于 2010-12-23T12:12:48.893 回答