生成不重复的随机整数序列，这些整数相差仅为1个比特。

Question

生成不重复的随机整数序列，这些整数相差仅为1个比特。

6

我需要生成一个N位整数的（伪）随机序列，其中相邻的整数仅在前一整数上有1个不同的位，并且该序列永远不会重复。我知道格雷码可以生成仅有1个位差异的不重复序列，而LFSR可以生成类似于随机的不重复序列，但我不确定如何将这些想法结合起来以产生我想要的结果。

实际上，N非常大，比如1000。我想要随机采样这个2^1000整数的大空间，但我需要生成类似于随机行走的东西，因为我所考虑的应用程序只能通过翻转一位从一个数字跳到另一个数字。

- Victor Liu

你想要采样多少个整数？（你的“随机”步长有多长？）走得越远，就越受限制（因为你不能重复），下一个整数也就越可预测。 - ShreevatsaR

我可能需要几百万到几千万个样本。大约2^20 - 2^25这样的数量级。我还对几乎不重复的算法感兴趣（少量重复也可以接受）。这是为了蒙特卡罗模拟。 - Victor Liu

3

@Victor：啊，真正的蒙特卡罗模拟是使用没有“永不重复”约束的随机漫步来完成的。实际上，如果添加一个像“永不重复”的约束条件，那么结果就不再是马尔可夫过程了，并且大多数关于蒙特卡罗模拟的定理都不适用。如果你的应用确实是蒙特卡罗模拟，那么Ethan的答案很好，你应该接受它。 - ShreevatsaR

是的，我知道蒙特卡罗通常允许重复，但在这里我使用术语比较宽泛。对于我的应用程序，我更希望更好地覆盖采样空间，因为我想根据整数确定概率分布。 - Victor Liu

1

“从不重复”是严格要求吗？还是“仅极少重复”就足够了？ - nibot

@Victor：当然，蒙特卡罗方法适用于任意概率分布（事实上，洛斯阿拉莫斯的原始论文就是使用它来计算某些难以评估的概率分布所产生的积分）。"不重复"约束并不能给你“更好地覆盖样本空间”，这只会导致非马尔可夫过程和错误的结果。如果您更仔细地描述您所需的概率分布，我或其他人可能会解释您需要哪种随机漫步。 - ShreevatsaR

3个回答

1

这让我想起了分形 - 沿着Julia集合的边界或类似的东西。

如果N为1000，则使用一个2^500 x 2^500的分形位图（显然不要提前生成它 - 您可以按需推导每个像素，并且大多数像素不需要）。每个像素移动都是沿着像素之间的边界线向上、向下、向左或向右的一个像素，就像简单的位图跟踪算法一样。只要您从位图的边缘开始，您应该迟早会返回到位图的边缘 - 沿着特定的“颜色”边界始终应该给出没有自交的闭合曲线，如果您查看该分形的无界版本。

当然，位图的x和y轴坐标将需要“格雷编码” - 有点像超大型Karnaugh地图。跟踪中的每个步骤（向上、向下、向左或向右的一个像素）相当于一个位图坐标中的单比特更改，因此在随机行走的结果值中的一个位上也会发生单比特更改。

编辑

我刚意识到有一个问题。边界越皱，你在跟踪中遇到选择方向的点的可能性就越大，例如...

 * | .
---+---
 . | *

无论您从哪个方向进入这个点，都有三种出路可选。选择另外两个中的错误之一可能会使您返回到此点，因此这是一个可能的自交点和可能的重复。您可以消除“继续朝同一方向前进”的选择 - 无论您转向哪个方向，应该保持相同的边界颜色在您追踪的边界路径的左右两侧 - 但这仍然留下了两个方向的选择。

我认为可以通过在分形中至少使用三种颜色，并始终将同一颜色保持在边界的某一特定侧（相对于追踪方向）来消除问题。虽然可能有一个“只要分形不太皱”的限制。

最后的解决方法是记录此选择可用的点。如果您返回到相同的点，请返回并选择另一种选择。

- user180247

0

当像这样的算法：

seed()
i = random(0, n)
repeat:
    i ^= >> (i % bitlen)
    yield i

如果要返回一个随机的整数序列，每个整数之间相差1位，那么需要一个巨大的数组来进行回溯，以确保数字的唯一性。此外，随着回溯密度的增加，您的运行时间将呈指数级增长，因为在序列中每增加一个数字，命中新的且不重复的数字的几率就会降低。

为了减少时间和空间，可以尝试其中之一：

Bloom Filter

使用Bloom过滤器可以大大减少唯一性回溯所需的空间（和时间）。

由于Bloom过滤器偶尔会产生误报，因此在您的序列中会出现一定比例的错误检测到的重复项（因此被跳过）。

虽然使用Bloom过滤器可以减少空间和时间，但您的运行时间仍将呈指数级增长...

Hilbert Curve

一个希尔伯特曲线表示在二次平面（或立方体）上进行的非重复的(一种伪随机的)行走，每步长度为1。
使用 希尔伯特曲线（在适当的值分布上）可能会完全消除需要回溯的需求。为了使你的序列得到种子，你会生成0到s（s是你的平面/立方体/超立方体的边长）之间的n个（n为你的平面/立方体/超立方体的维度）随机数。 希尔伯特曲线不仅可以消除回溯的需求，还可以让序列运行在每个数字的O(1)时间内（与使用回溯相比，后者会使您的运行时间呈指数级增加...）
要为您的序列生成种子，您将通过每个维度的随机位移来包装移动您的n维分布。

注：您可能会在此处获得更好的答案：StackExchange 的 CSTheory （或者不会，参见评论）

- Regexident

希尔伯特曲线非常可预测 - 它是否可以被称为伪随机取决于应用程序。格雷码已经被提到过了，而且格雷码和希尔伯特曲线之间存在着某种关系。 - user180247

@Steve314：嗯，没有种子或相等的种子，rand()将生成相同的序列，被认为是伪随机。不过你说得好。我忘记在我的答案中提到一种可能的播种方式了。现在已经添加了。基本上是用随机种子进行随机位移移位，并用随机种子进行封装。因此，虽然它总是会生成相同的模式，但实际数字序列的顺序高度取决于种子的移位距离和分布的性质。 - Regexident

使用布隆过滤器可以防止产生重复项。假阳性会阻止生成一个唯一的数字，该数字与已经生成的数字哈希到相同的值。 - Jim Mischel

@jim-mischel：完全正确。已修复。我想我需要睡一会儿。 ;) - Regexident

话虽如此，布隆过滤器将是解决这个问题的极好选择。我们需要在2^1000的空间内生成2^25个数字。一个N=2^25且误判率为百万分之一的布隆过滤器只需要大约120 MB的空间。您可以通过容忍更多的误判来减少内存需求（以及计算密钥的成本），但在这种情况下，这很可能不会对结果产生负面影响。 - Jim Mischel

一组绝对零误差的布隆过滤器比一个简单列表占用更多的空间。顺便说一句，除非是实际研究兴趣的问题，请不要推荐cstheory.stackexchange——它不是Stack Overflow的等价物，而是像MathOverflow一样只针对研究人员社区感兴趣的问题的网站。 - ShreevatsaR

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

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

- Ethan Cabiac · Accepted Answer

使用任何随机数生成算法生成1到N（或0到N-1，具体取决于语言）之间的整数。使用结果确定要翻转的位的索引。

为了满足随机性，您需要存储先前生成的数字（感谢ShreevatsaR）。此外，您可能会遇到无法找到非重复答案的情况，因此还需要使用回溯算法。