更好的随机“感觉”整数生成器，用于短序列

Question

我正在尝试找到一种创建短序列内“感觉”随机的随机数的方法。这是用于问答游戏的，其中有四个可能的选项，软件需要选择其中一个位置放置正确答案，然后用干扰项填充其他三个选项。

显然，arc4random % 4在长序列上会产生足够随机的结果，但在短序列中完全有可能（并且经常发生！）连续返回五个或六个相同的数字。这就是我想要避免的。

我也不想简单地说“永远不要两次选择同一个方格”，因为这将导致除第一个问题外每个问题只有三个可能的答案。目前，我的做法类似于以下内容：

bool acceptable = NO;
do {
  currentAnswer = arc4random() % 4;
  if (currentAnswer == lastAnswer) {
    if (arc4random() % 4 == 0) {
      acceptable = YES;
    }
  } else {
    acceptable = YES;
  }
} while (!acceptable);

有没有更好的解决方案我忽略了什么？

- John Biesnecker

---

我认为这个答案将强烈依赖于有多少个四面体“硬币”连续出现，因为可能没有足够短的序列的解决方案。你确实抓住了自由度减少的问题，但我的直觉告诉我，任何事后选择过程都会减少自由度。在你的例子中，A后面跟着A的后验概率变成了1/16，而不是A、B的1/4。即使玩家没有注意到她已经注意到了，我也期望她会注意到这一点。人类非常擅长这个（鸽子也是）。 - msw

我应该指出这些序列是开放式的。我认为对于大多数玩家来说，它们会相对较短（少于100个），但理论上你可以玩几个小时并回答成千上万个问题。我不认为这太重要，因为玩家不太可能记得超过几个问题的序列，尽管正如你所说，他们可能会注意到它，而不会注意到他们已经注意到了。 :) - John Biesnecker

Answer 1

你需要填充一个结果数组，然后shuffle它，最后按照顺序进行分配。

所以对于只有8个问题：

answer_slots = [0,0,1,1,2,2,3,3]

shuffle(answer_slots)

print answer_slots
 [1,3,2,1,0,2,3,0]

- Will

---

这很可能会产生随机的聚类，也可能不会。 - msw

@msw：它们只会和你允许的一样长。如果你在洗牌"0..3*3"，那么同一个数字最多只会出现三次。 - Joey

如果集合长度仅为8，则有87％的可能集合至少具有一个相邻元素。在这种情况下，你无法做得更好。 - msw

Answer 2

如果你的问题是如何在不迭代的情况下计算currentAnswer，Guffa已经回答了你的问题。

如果问题是如何避免随机聚类而不违反等概率性，并且你知道列表长度的上限，则考虑以下算法，它有点像非排序：

from random import randrange
# randrange(a, b) yields a <= N < b

def decluster():
    for i in range(seq_len):
        j = (i + 1) % seq_len
        if seq[i] == seq[j]:
            i_swap = randrange(i, seq_len) # is best lower bound 0, i, j?
            if seq[j] != seq[i_swap]:
                print 'swap', j, i_swap, (seq[j], seq[i_swap])
                seq[j], seq[i_swap] = seq[i_swap], seq[j]

seq_len = 20
seq = [randrange(1, 5) for _ in range(seq_len)]; print seq
decluster(); print seq
decluster(); print seq

请注意，本文与实际的Python代码没有任何关联。我相信先前的概率已经得到维护，并且似乎会破坏一些聚类（有时也会添加一些）。但是我很困，所以这只是为了娱乐目的。

- msw

---

太棒了。我最终实现了类似这样的东西。游戏是开放式的，所以我只是在一排中生成100个值，当这些值用完时再生成100个。它肯定比我的方法更“随机”。 - John Biesnecker

感谢这个有趣的问题。经过一天的思考，我非常确定如果使用一个像 arc4 这样的良好 PRNG，拉斯维加斯游戏委员会会批准这个算法是“均匀”的。 - msw

msw：我怀疑他们不会允许使用PRNG，无论是否具有加密安全性 :-）。我可以尝试为我们的RNG创建一个装饰器，并通过我们的测试运行此装饰器。但是，如果您避免聚类，您也会放弃大量可能的结果。等概率性不仅适用于单比特测试，还可以查看更大的段落。话虽如此，在这个问题上，它肯定是正确的 - 通常情况下通常是一个坏主意;-)。 - Joey

@Johannes：我想我理解了你的评论，但是decluster算法是否从结果空间中删除任何序列并不明显。我知道我将会花费大量的计算时间来找出答案。如果i_swap的下限为零，我认为我可以证明它，如果是i，那么我不太确定，但明天就会弄清楚。 - msw

Answer 3

设置一个加权数组。假设最后一个值是2。创建一个如下的数组：

array = [0,0,0,0,1,1,1,1,2,3,3,3,3];

接着从数组中选择一个数字。

newValue = array[arc4random() % 13];

现在改用数学计算，而不是数组。

newValue = ( ( ( arc4random() % 13 ) / 4 ) + 1 + oldValue ) % 4;

对于P个可能性和权重为0<W<=1的情况，请使用：

newValue = ( ( ( arc4random() % (P/W-P(1-W)) ) * W ) + 1 + oldValue ) % P;

对于P=4和W=1/4，(P/W-P(1-W)) = 13。这意味着最后一个值出现的可能性只有其他值的1/4。

如果你完全消除了最近的答案，那么它将与最近的答案过于频繁出现一样引人注目。我不知道什么权重会让你感觉合适，但1/4是一个很好的起点。

- drawnonward

Answer 4

为了将重复数字的概率降低25％，您可以从0到3.75之间随机选择一个数字，然后旋转它，以便0.75出现在先前的答案上。

为避免使用浮点值，您可以将因子乘以四：

伪代码（其中 / 是整数除法）：

currentAnswer = ((random(0..14) + lastAnswer * 4) % 16) / 4

- Guffa