如何生成一个从0到n的重复整数序列？

Question

我正在尝试编写一些代码来创建一个伪随机整数序列，该序列使用从 0 到 n 的每个数字，然后重复。天真的方法是创建一个包含 n 个整数的数组，然后以某种方式打乱它们，然后循环遍历它们。那是用 space 换取速度，但我需要尽可能保留 space。

想到这个让我想起了“FizzleFade”，Wolfenstein 3D 用于用红色填充屏幕的算法，一次一个像素，而不是两次填充相同的像素。很简单（这个例子只是打印X和Y坐标）：

    uint32_t rndval = 1;
    uint16_t x, y;
    do {
        y = rndval & 0x000FF;
        x = (rndval & 0x1FF00) >> 8;
        unsigned lsb = rndval & 1;
        rndval >>= 1;
        if (lsb) {
            rndval ^= 0x00012000;
        }
        if (x < 320 && y < 200)
            printf("x: %d y: %d\n", x, y);
    } while (rndval != 1);

至少，看起来很简单。这似乎是一个线性反馈移位寄存器。但是，我不知道如何将此代码改编为 n 位。我不知道他们是如何确定 XOR 值的。我首先尝试将上面的代码调整为 8 位值，如下所示：

#include <stdio.h>
#include <stdint.h>

int fizzlefade(void) {
    uint8_t rndval = 1;
    uint16_t values = 0;
    do {
        unsigned lsb = rndval & 1;
        rndval >>= 1;
        if (lsb) {
            rndval ^= 0x21;
        }
        printf("%d\n", rndval);
        values++;
    } while (rndval != 1);
    printf("Total number of values: %d\n", values);
    return 0;
}

int main(void) {
    printf("Fizzlefade demo\n");
    fizzlefade();
    return 0;
}

但是，无论我将异或值更改为什么，我都只能得到 N 个值，其中 N < n，对于一个 8 位值，通常少于 100 个值。我如何确定异或抽头？我需要不同的起始值吗？除了使用 LFSR，还有 faster/smaller 方法吗？

编辑：我取得了一些进步。我注意到在原来的情况下，rndval 是输出值大小的两倍。所以我将我的 rndval 更改为 16 位无符号，然后将 XOR 更改为 0x1200 以模仿原始代码。这给了我 250 个随机值，所有值都是独一无二的——非常接近！仍然不确定该怎么做。

Answer 1

（我得运行... 但这是一个基于质数和模数的快速答案。

#include <stdio.h>
 
int main(void) {
    int max = 20;
    int prime = 29;
 
    for(int i=0; i<max; ++i)
    {
        int p_rand = (i*prime) % max + 1;
        printf("Pseudo Random: %d\n", p_rand);
    }
 
    return 0;
}

输出

Pseudo Random: 1
Pseudo Random: 10
Pseudo Random: 19
Pseudo Random: 8
Pseudo Random: 17
Pseudo Random: 6
Pseudo Random: 15
Pseudo Random: 4
Pseudo Random: 13
Pseudo Random: 2
Pseudo Random: 11
Pseudo Random: 20
Pseudo Random: 9
Pseudo Random: 18
Pseudo Random: 7
Pseudo Random: 16
Pseudo Random: 5
Pseudo Random: 14
Pseudo Random: 3
Pseudo Random: 12

（1到20的所有数字，无重复，伪随机排列）

如何生成一个从0到n的重复整数序列？

How to generate a repeating integer sequence from 0 to n?

c

integer

lfsr

输出