java - 在 3 维空间中移动所有点而不存储所有可能的坐标

Question

我正在编写一个 3 维元胞自动机。我现在在每一代中迭代它的方式是:

1. 创建 3D 空间中所有可能坐标的列表。
2. 打乱列表。
3. 遍历列表，直到访问了所有坐标。
4. 转到 2。

代码如下:

我有一个简单的 3 整数结构

public class Coordinate
{
    public int x;
    public int y;
    public int z;

    public Coordinate(int x, int y, int z) {this.x = x; this.y = y; this.z = z;}
}

然后在某个时候我会这样做:

List<Coordinate> all_coordinates = new ArrayList<>();
[...]
for(int z=0 ; z<length ; z++)
{
    for(int x=0 ; x<diameter ; x++)
    {
        for(int y=0 ; y<diameter ; y++)
        {
            all_coordinates.add(new Coordinate(x,y,z));
        }
    }
}

然后在主要算法中我这样做:

private void next_generation() 
{ 
    Collections.shuffle(all_coordinates);
    for (int i=0 ; i < all_coordinates.size() ; i++) 
    {
        [...]
    }
}

问题是，一旦自动机变得太大，包含所有可能点的列表就会变得巨大。我需要一种方法来随机播放所有点，而不必实际将所有可能的点存储在内存中。我该怎么办？

Answer 1

实现此目的的一种方法是首先将三维坐标映射到单一维度。假设你的三个维度的大小是 X、Y 和 Z。所以你的 x 坐标从 0 到 X-1，等等。你的空间的完整大小是 X*Y*Z。我们将其称为 S。

要将 3 空间中的任何坐标映射到 1 空间，您可以使用公式 (x*X) + (Y*y) + z。

当然，一旦生成数字，就必须转换回 3 维空间。反转上面的转换很简单。假设 coord 是 1-space 坐标:

x = coord/X
coord = coord % X
y = coord/Y
z = coord % Y

现在，通过使用单一维度，您已将问题简化为以伪随机顺序生成从 0 到 S 的所有数字，而不会重复。

我知道至少有三种方法可以做到这一点。最简单的使用 multiplicative inverse ，正如我在这里展示的:Given a number, produce another random number that is the same every time and distinct from all other results .

生成所有数字后，您可以通过选择不同的 x 和 m 值来“重新洗牌”列表以进行乘法逆计算。

在特定范围内创建非重复伪随机序列的另一种方法是使用 linear feedback shift register .我没有现成的例子，但我已经使用过它们。要更改顺序(即重新洗牌)，您需要使用不同的参数重新初始化生成器。

您可能也对这个问题的答案感兴趣:Unique (non-repeating) random numbers in O(1)? .该用户只查找 1,000 个数字，因此他可以使用表格，而接受的答案反射(reflect)了这一点。其他答案包括 LFSR 和 Linear congruential generator是有特定时期设计的。

我提到的所有方法都不需要您保持很多状态。无论您的范围是 20 还是 20,000,000，您需要维护的状态量都是恒定的。

请注意，我上面提到的所有方法都给出了伪随机序列。它们不会是真正随机的，但它们可能足够接近随机以满足您的需要。