如何使用可逆种子使所有可能的列表组合？

Question

我想拥有一个由100个项目制成的列表，每个项目都是0-31的值。然后，我希望能够获取以下列表之一，并知道随机生成该确切列表的必要种子/输入。

Answer 1

使用一些适当的线性一致生成器：

您可以使用Pierre L'Ecuyer的这篇研究论文：

表rer” > LCGS IS 2 ³⁰ ，接近10亿。参见论文的表4。只需选择其中一个LCG，例如：

u _{n + 1} =（（（（116646453） * un ） + 5437）mod 2 ³⁰

您的物品正好宽5位。如果您决定将项目6乘6分组，则每个 group 恰好宽30位，因此可以被视为此Modulo 2 ³⁰ lcg的一个状态。

从最初的6个项目组中，LCG的一个步骤将生成下一个组，即接下来的6个项目。论文告诉您，意甲总体上看起来是合理的随机。

因此，您可以将前6个项目视为“种子”，因为您可以从最左边的6个项目中重建整个列表。

即使假设为了混淆，您在种子之后启动了列表的可见部分，您仍然只有大约十亿个可能的种子可以担心。任何体面的计算机都可以通过少数几秒钟的时间在几秒钟内通过蛮力找到剩下的种子，并通过为每种可能的种子模拟LCG并与实际列表进行比较。

示例Python代码：

一个人可以从创建一个类别的类中开始，该类给定种子，提供了一个无限的意甲，在0到31之间的项目：

class LEcuyer30:
   def  __init__ (self, seed):
       self.seed      = seed & ((1 << 30) - 1)
       self.currGroup = self.seed
       self.itemCount = 6

   def __toNextGroup(self):
       nextGroup = ((116646453 * self.currGroup) + 5437) % (1 << 30)
       self.currGroup = nextGroup
       self.itemCount = 6

   def  getItem(self):
       if (self.itemCount <= 0):
           self.__toNextGroup()

       # extract 5 bits:
       word = self.currGroup >> (5 * (self.itemCount - 1))
       self.itemCount -= 1
       return (word & 31)

测试代码：

我们可以创建20个项目的序列并打印它：

# Main program:

randomSeed = 514703103
rng = LEcuyer30(randomSeed)

itemList = []
for k in range(20):
    item = rng.getItem()
    itemList.append(item)

print("itemList = %s" % itemList)

程序输出：输出：

itemList = [15, 10, 27, 15, 23, 31, 1, 10, 5, 15, 16, 8, 4, 16, 24, 31, 7, 5, 8, 19]