javascript - 如何以始终生成唯一值的方式确定性地组合整数？

Question

我有一个 set 随机生成的整数，以及一个 evolve(set) 函数，它采用一个集合，删除两个整数并插入 4 个新整数。我希望集合永远不会有重复的整数。也就是说，无论我应用多少次 evolve(evolve(...evolve(set)))，它都不应该有重复值。

combine(int x, int y) -> int 的简单选择是什么，可以保证该属性的概率很高？

示例:

// Helpers.
var range = length => Array.from({length}, i => i);
var random = () => (Math.random() * Math.pow(2,31) | 0);
var removeRandom = set => set.splice(random() % set.length, 1)[0];
var hasRepeated = set => !set.sort((a,b) => a - b).reduce((a,b) => a && a !== b && b || 0, -1);

// Receives two parent ints, returns 4 derived ints.
// Can't use random() here; it must generate 4 ints
// from simple functions (multiplication, bitwise
// operations, etc.) of `a` and `b`.
function combine(a, b) {
  return [a + b + 0, a + b + 1, a + b + 2, a + b + 3];
};

// Removes two ints from set, inserts 4 ints.
function evolve(set) {
  var a = removeRandom(set);
  var b = removeRandom(set);
  set.push(...combine(a,b));
};

// Random initial set of ints.
var set = range(64).map(random);

// No matter how many times `evolve` is applied, 
// the set should never have repeated ints.
for (var i = 0; i < 50000; ++i) {
  evolve(set);
}

// Prints `true` if algorithm is correct
// (no repeated number was generated).
console.log(!hasRepeated(set));

请注意，此处 combine(a,b) 只是将它们相加。这是一个糟糕的选择；只需调用 50000 次 evolve，它就已经无法通过测试。我可以使用线性同余生成器，但我想知道在那些条件下它是否可以比它更简单。也许使用 XOR？

Answer 1

如果你有足够的空间来保存一个包含所有可能条目的数组，你可以将它随机化，然后跟踪绑定(bind)你的集合的索引，递增起始索引以删除元素和递增结束索引以添加它们.

您可以预先随机化整个数组，也可以在结束索引递增时随机化。