代码之家  ›  专栏  ›  技术社区  ›  pauldoo

在不预先构建整个列表的情况下,以随机顺序生成整数序列[duplicate]

  •  2
  • pauldoo  · 技术社区  · 16 年前

    如何生成从1到N的整数列表,但以随机顺序,而不在内存中构建整个列表?

    (需要明确的是:生成的列表中的每个数字必须只出现一次,因此它必须相当于先在内存中创建整个列表,然后再进行洗牌。)

    这已被确定为 this question .

    4 回复  |  直到 8 年前
        1
  •  1
  •   lakshmanaraj    16 年前

    非常简单的随机数是1+((幂(r,x)-1)mod p)对于x从1到p的值将是从1到p的,并且将是随机的,其中r和p是素数,r<>P

        2
  •  0
  •   paxdiablo    16 年前

    从技术上讲,不是整个列表,但您可以使用位掩码来确定是否已经选择了一个数字。它的存储空间比数字列表本身少得多。

    将所有N位设置为0,然后针对每个所需数字:

    • 使用常规线性同余方法之一选择1到N之间的数字。
    • 如果该数字已被使用,请使用wrap查找下一个最高未使用位(0位)。
    • 将数字位设为1并返回。

    这样,你就可以保证每个数字只使用一次,并且结果相对随机。

        3
  •  -1
  •   Fionn    16 年前

    指定一种您正在搜索解决方案的语言可能会有所帮助。

    你可以使用一个动态列表来存储你生成的号码,因为你需要一个你已经创建的号码的参考。每次创建一个新号码时,你都可以检查该号码是否包含在列表中,如果包含,则将其丢弃,然后重试。

    如果没有这样一个列表,唯一可能的方法是使用一个不太可能生成像 UUID 如果算法工作正常——但这并不能保证不会生成任何副本——那就不太可能了。

        4
  •  -1
  •   Quassnoi    16 年前

    你需要至少一半的总记忆,才能记住你已经做了什么。

    如果你的记忆力很差,你可以试试:

    1. 将迄今为止生成的结果保存在树中,随机化数据,并将其插入树中。如果无法插入,则生成另一个数字,然后重试,等等,直到树填满一半。

    2. 当树填充到一半时,你将其反转:你构建一棵树,其中包含尚未使用的数字,然后按随机顺序拾取它们。

    它在保持树结构方面有一些开销,但当指针的大小比数据的大小小得多时,它可能会有所帮助。