可以采用递增计数器并使其唯一随机出现的算法或公式 [英] Algorithm or formula that can take an incrementing counter and make it appear uniquely random

问题描述

我想知道是否有某种通用公式可以采用单个递增整数，然后通过模数运算将其运行到一个随机位置，以便在递增计数器时将其输出值递增跳来跳去，显得随机，但没有值被击中过两次.假设对一组数字有一些限制，例如16位整数(65536个整数)或32位整数等.也许不知道有一种方法可以使数字螺旋下降.该序列是可以预见的，但对于外行来说，它看起来似乎是随机的，而无需考虑太多.

I am wondering if there is a general formula of some sort that can take a single incrementing integer, and run it through a modulus sort of thing to shift it to a random place, so as you increment the counter, its output value jumps around and appears random, yet no value is ever hit twice. Assuming some limit on the set of numbers like 16-bit integers (65536 integers), or 32-bit integers, etc.. Perhaps there is a way to spiral numbers down somehow, I don't know. The sequence would be predictable, but to a layman it would appear random without thinking much of it.

例如，您可以将数字乘以2，以使其不会直接递增显示.但这不是很复杂.您也许可以将数字从集合的中间开始(例如30103表示16位整数)，然后乘以2并使用模数旋转数字，这似乎会增加得更少.但是您仍然可以看到一种模式.

For example, you can multiply a number by 2 to make it not appear directly incremented. But that's not very sophisticated. You could perhaps start the number at the middle of the set (like 30103 for 16-bit integers), then multiply by 2 and rotate the numbers using a modulus, and this would appear even less incremented. But you could still see a pattern.

我想知道可以通过哪种类型的模式或方程式(以有界整数集)运行递增的数字，以使输出看起来尽可能不可预测，并且同时永远不会命中相同的数字两次.这样，您可以使ID看起来是随机生成的，而不必事先将所有ID随机存储在数据库中.该公式将从单个存储的整数生成它们.在这方面有什么可能，方程式是什么?理论上它能走多远?

I'm wondering what sorts of patterns or equations you could run an incremented number through (in a bounded set of integers) so that the output appears the least predictable as possible, and at the same time it never hits the same number twice. This way you could make IDs appear randomly generated to the layman without having to store all the IDs in a database in random order in advance. The formula would generate them from a single stored integer. What is possible in this regard, and what is the equation? How far can it theoretically go?

也许您可以使集合为奇数，并跳过第20个数字，并以某种方式证明它最终将遍历整个集合而无重复.但我无法弄清楚.

Maybe you could make the set odd, and skip every 20th number, and somehow prove that it will eventually revolve through the whole set without repeats. I can't figure this out though.

更新:这似乎在伪随机数生成的字段中，例如此，但是我不确定它们是否符合永远不要重复号码.

Update: This seems to be in the field of pseudorandom number generation, like this, but I'm not sure if they fit the added constraint of never repeating the number.

此处是我发现并实现的内容，但它给出了一些重复的内容:/.

Here is what I found and implemented, but it's giving some duplicates :/.

const fetch = (x, o) => {
  if (x >= o) {
    return x
  } else {
    const v = (x * x) % o
    return (x <= o / 2) ? v : o - v
  }
}

const fetch32 = (x) => fetch(x, 4294967291)
const fetch16 = (x) => fetch(x, 65519)
const fetch8 = (x) => fetch(x, 251)

// the last number can be anything.
const build32 = (x, o) => fetch32((fetch32(x) + o) ^ 1542469173)
const build16 = (x, o) => fetch16((fetch16(x) + o) ^ 42703)
const build8 = (x, o) => fetch8((fetch8(x) + o) ^ 101)

let i = 0
let n = Math.pow(2, 32)
while (i < n) {
  let j = 0
  let r = {}
  while (j < n) {
    let x = build32(j, i)
    if (r[x]) throw `${i}:${j}:${x}`
    r[x] = true
    j++
  }
  i++
}

评论中的另一个链接问题未显示遵循唯一性约束的JavaScript实现.

The other linked question in the comment doesn't show a JavaScript implementation that adheres the the uniqueness constraint.

推荐答案

如果您正在寻找一个序列，其中一个值是通过知道先前的值来产生的，那么您所寻找的可能是一个线性同余生成器，模数为2的幂.其中涉及一些参数:

If you are looking for a sequence, where one value is produced from knowing what the previous value was, then what you are looking for could be a Linear congruential generator, with a modulus of a power of 2. There are a few parameters involved:

• m :模数，在您的情况下为2 ⁸ ，2 ¹⁶ 或2 ³²
• a :乘数.为了确保在生成第一个重复项之前生成所有值，该值必须是4加1的倍数(假设 m 是2的幂).
• c :增量.一定很奇怪.

• m: the modulus, which in your case is 2⁸, 2¹⁶, or 2³².
• a: the multiplier. To ensure that all values are produced before the first duplicate is generated, this must be a multiple of 4 plus 1 (assuming m is a power of 2).
• c: the increment. It must be odd.

您可以使用这些数字来得出您对随机性"感到满意的系列.

You can play with these numbers to arrive at a series that you are satisfied with in terms of "randomness".

以上引用的Wikipedia文章列出了一些伪随机生成器中使用的一些参数选择.我刚刚选择了 a = 97 和 c 距离范围一半的奇数.

The above referenced Wikipedia article lists some parameter choices that are used in some pseudo random generators. I have just selected a=97 and c some odd number half way the range.

以下代码可证明其唯一性:

Here is some code to prove the uniqueness:

/*
    Assuming that m is a power of 2:
    - c must be odd
    - a % 4 must be 1
*/
function createFetch(m, a, c) { // Returns a function
     return x => (a * x + c) % m;
}
const m = 2**16;
const fetch16 = createFetch(m, 97, (m>>1)-1);

const r = new Set;
let x = 1;
for (let i = 0; i < m; i++) {
    x = fetch16(x);
    if (i < 10) console.log(x);
    if (r.has(x)) throw `${i}:${x}`
    r.add(x);
}
console.log("...");
console.log(`generated ${r.size} unique numbers`);

NB/这是生成器的一个很好的用例，在JavaScript中看起来像这样:

NB/ this is a good use case for a generator, which in JavaScript looks like this:

function * fetch(m, a, c, x=1) {
     while (true) {
         x = (a * x + c) % m;
         yield x;
     }
}
const m = 2**16;
const fetch16 = fetch(m, 97, (m>>1)-1);

const r = new Set;
for (let i = 0; i < m; i++) {
    x = fetch16.next().value;
    if (i < 10) console.log(x);
    if (r.has(x)) throw `${i}:${x}`
    r.add(x);
}
console.log("...");
console.log(`generated ${r.size} unique numbers`);

这篇关于可以采用递增计数器并使其唯一随机出现的算法或公式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！