给定范围内的所有数字但顺序是随机的

Question

给定范围内的所有数字但顺序是随机的

mathrandomrangetheorygenerated

8

假设我想以随机顺序生成1-1000之间的所有整数，但是...

不能重复生成数字
没有存储所有可能数字的数组、列表...
没有存储已生成的数字。
最终不能缺少任何数字。

我认为这是不可能的，但也许我没有考虑正确的解决方案。

我想在C#中使用它，但我更感兴趣的是方法而不是实际实现。

- K. Torrance

“随机”到底有多随机？你只需要看起来随机就行了吗？还是需要通过统计测试？或者需要具备密码学强度的随机性？ - Mark Dickinson

随机性并不是非常重要的，它甚至可以遵循某种模式，只要不漏掉任何数字即可。我认为我应该将其添加到列表中，以明确不能缺少任何数字。 - K. Torrance

1

你可以尝试使用“伪随机置换”作为搜索词：其思想是将这样的置换应用于固定序列1、2、3、...，以获得伪随机序列。分块密码是伪随机置换的一种可能来源。 - Mark Dickinson

1

@Spektre：楼主说“不使用数组、列表等存储所有可能的数字”，所以那种方法行不通。 - Chris

2

我对这些接近的投票感到惊讶；在我看来，这似乎是一个定义明确的问题（@rossum的答案表明它在实践中是可回答的）。 - Mark Dickinson

显示剩余2条评论

2个回答

4

如果随机性不是主要问题，您可以使用线性同余生成器。由于当模数为质数时，LCG将不会产生最大长度序列，因此您需要选择较大的模数（下一个最高幂次方是一个明显的选择），并跳过所需范围外的任何值。

我很抱歉C#实际上不是我的专长，但希望以下Python代码是自解释的。如果您想生成非常小范围内的序列，则需要进行一些微调:

# randint(a, b) returns a random integer in the range (a..b) (inclusive)
from random import randint

def lcg_params(u, v):
    # Generate parameters for an LCG that produces a maximal length sequence
    # of numbers in the range (u..v)
    diff = v - u
    if diff < 4:
         raise ValueError("Sorry, range must be at least 4.")
    m = 2 ** diff.bit_length()              # Modulus
    a = (randint(1, (m >> 2) - 1) * 4) + 1  # Random odd integer, (a-1) divisible by 4
    c = randint(3, m) | 1                   # Any odd integer will do
    return (m, a, c, u, diff + 1)

def generate_pseudorandom_sequence(rmin, rmax):
    (m, a, c, offset, seqlength) = lcg_params(rmin, rmax)
    x = 1         # Start with a seed value of 1
    result = []   # Create empty list for output values
    for i in range(seqlength):
        # To generate numbers on the fly without storing them in an array,
        # just run the following while loop to fetch a new number
        while True:
            x = (x * a + c) % m             # Iterate LCG until we get a value in the
            if x < seqlength: break         # required range
        result.append(x + offset)           # Add this value to the list
    return result

例子：

>>> generate_pseudorandom_sequence(1, 20)
[4, 6, 8, 1, 10, 3, 12, 5, 14, 7, 16, 9, 18, 11, 20, 13, 15, 17, 19, 2]

- r3mainer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rossum · Accepted Answer

加密。加密是两个集合之间的一对一映射。如果这两个集合相同，则它是由加密密钥指定的置换。编写/查找一种将{0, 1000}映射到自身的加密方式。在此处阅读Format Preserving Encryption (FPE)。

为了生成随机顺序，只需按顺序加密数字0、1、2等。您不需要存储它们，只需跟踪您已经通过列表走了多远。

从实用角度来看，使用{0, 1023}中的数字会更容易处理，因为这将是一个块密码，块大小为10位，您可以编写一个简单的Feistel cipher来生成您的数字。您可能仍然想这样做，并重新加密超过1000的数字--即FPE的周期行走方法。