以伪随机顺序访问网格中的每个单元而不使用临时存储

this SO question . 它有一些有用的答案和参考资料。

编辑

Linear Feedback Shift Register . wikipedia页面显示了如何设置从1到19位长的最大LSFR,并且有一个指向PDF的链接,该链接具有最多168位长的寄存器设置。实现一个算法应该不难,该算法将为您提供从1到任意N的伪随机值

// a 31 bit LFSR
// based on http://forums.sun.com/thread.jspa?threadID=5276320
public static int getNextValue(int register) {
    int t31 = (register & (1 << 30)) >>> 30; 
    int t28 = (register & (1 << 27)) >>> 27;
    int input = t31 ^ t28;
    register <<= 1;
    register |= input;
    register &= 0x7fffffff; // mask with this to ensure 0s in the high order bits
    return register;
}

public static int getNextValueBelowN(int value, int n) {
    do {
        value = getNextValue(value);
    } while (value > n);
    return value;
}

后一个函数的一个明显优化是分析N并找到最接近它的位长度的LFSR函数,这将最小化while循环中的未命中

结束编辑

在第二部分中,只点击较低的三角形意味着您需要减少N并改变将一维索引转换为二维索引的方式。例如:

public static int getMaxValue(int dimension) {
    int retVal = 0;
    while (dimension > 0) {
        retVal += dimension--;
    }
    return retVal;
}


public static int getMaxValueFast(int dimension) {
    int retVal = 0;
    if (dimension % 1 == 1) {
        retVal += dimension--;
    }
    retVal += ((dimension + 1) * dimension / 2);
    return retVal;
}



public static Point getCoordinates(int index, int dimension) {
    Point retVal = new Point();
    while (index >= dimension) {
        ++retVal.x;
        index -= dimension--;
    }
    retVal.y = index;
    return retVal;
}

对于下三角,您还可以使用标记过程来跟踪您已经访问过的对象,但现在在生成整数时 i 和 j ,如果有的话,把它扔掉 我 等于 J 否则就使用元组 (i, j) 如果 i > j (j, i) j > i .