混洗数组，同时使每个索引在任何索引中的概率相同

Question

我想打乱一个数组，并且每个索引在任何其他索引（不包括它自己）中都有相同的概率。

我有这个解决方案，只有我发现最后两个索引总是会相互交换：

void Shuffle(int arr[]. size_t n)
{
  int newIndx = 0;
  int i = 0;

  for(; i > n - 2; ++i)
  {
    newIndx = rand() % (n - 1);
    if (newIndx >= i)
    {
      ++newIndx;
    }

    swap(i, newIndx, arr);
  }
}

但最终可能有些索引会再次回到原来的位置。

有什么想法吗？

朗。

Answer 1

的对号（洗牌），其中没有元素在它原来的地方被称为紊乱。

生成随机乱序比生成随机排列更难，可以在线性时间和空间中完成。（生成随机排列可以在线性时间和恒定空间中完成。）这里有两种可能的算法。

最容易理解的解决方案是拒绝策略：进行 Fisher-Yates shuffle，但如果 shuffle 尝试将元素放在其原始位置，则重新启动 shuffle。[注1]

由于随机 shuffle 是混乱的概率大约为 1/ e，因此执行的 shuffle 的预期次数约为e（即 2.71828…）。但是由于不成功的shuffle一遇到第一个不动点就重新开始，shuffle的总步数小于数组大小的e倍，详细分析见这篇论文，证明了期望随机数需要的个数算法大约是 ( e ?1) 倍元素的数量。

为了能够进行检查并重新启动，您需要保留一个索引数组。下面的小函数产生了从 0 到 的索引的混乱n-1；然后有必要将置换应用于原始数组。

/* n must be at least 2 for this to produce meaningful results */
void derange(size_t n, size_t ind[]) {
  for (size_t i = 0; i < n; ++i) ind[i] = i;
  swap(ind, 0, randint(1, n));
  for (size_t i = 1; i < n; ++i) {
    int r = randint(i, n);
    swap(ind, i, r);
    if (ind[i] == i) i = 0;
  }
}

以下是该代码使用的两个函数：

void swap(int arr[], size_t i, size_t j) {
  int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}

/* This is not the best possible implementation */
int randint(int low, int lim) {
  return low + rand() % (lim - low);
}

以下函数基于 Conrado Martínez、Alois Panholzer 和 Helmut Prodinger 于 2008 年发表的论文“Generating Random Derangements”，尽管我使用了不同的机制来跟踪周期。他们的算法使用大小的位向量，N但使用拒绝策略来找到尚未标记的元素。我的算法使用尚未操作的索引的显式向量。该向量的大小也是 ，N仍然是 O(N) 空间 [注 2]；由于在实际应用中，N不会很大，恕我直言，差异并不显着。好处是可以通过对随机数生成器的一次调用来选择要使用的下一个元素。同样，这并不是特别重要，因为预期MP&P 算法中的拒绝次数非常少。但对我来说似乎更整洁。

算法（MP&P 和我的）的基础是产生混乱的递归过程。重要的是要注意，乱序必然是一些循环的组合，其中每个循环的大小都大于 1。（大小为 1 的循环是一个不动点。）因此，大小为 N 的乱序可以由使用以下两种机制之一进行较小的紊乱：

• 产生N-1除 element 之外的元素的混乱N，并N在该循环中的任何点添加到某个循环中。为此，随机选择任何元素j在N-1周期和地点N后，立即j在j的周期。此替代方案涵盖N了大小 > 3 的循环中的所有可能性。

• 产生除 之外N-2的N-1元素的乱序N，并添加一个大小为 2 的循环，其中N的元素不是从较小的乱序中选择的。此替代方案涵盖N了大小为 2 的循环中的所有可能性。

如果是 size 的乱序数，从上面的递归不难看出：Dnn

Dn = (n−1)(Dn−1 + Dn−2)

乘数n?1在两种情况下都是：在第一种选择中，它指的是N可以添加的可能位置的数量，而在第二种选择中，它指的是选择n?2递归排列元素的可能方式的数量。

因此，如果我们要递归地产生大小为 的随机乱序N，我们将随机选择N-1前面的元素之一，然后就是否产生备选方案 1 或备选方案 2 做出随机布尔决定，由每个可能乱序的数量加权案件。

这种算法的一个优点是它可以扰乱任意向量；不需要像拒绝算法那样将置换索引应用于原始向量。

正如 MP&P 所指出的，递归算法可以很容易地迭代执行。这在备选方案 2 的情况下非常清楚，因为新的 2-cycle 可以在递归之前或之后生成，因此也可以先完成，然后递归只是一个循环。但对于备选方案 1 也是如此：即使在我们知道最终将进入哪个循环之前，我们也可以使元素N成为随机选择元素的循环中的后继者。如此看来，两个备选方案之间的差异减少为not 元素是否从未来的考虑中删除。jjj

如递归所示，应该以概率 选择备选方案 2 ，这就是 MP&P 编写算法的方式。我使用了等效的公式，主要是因为我的原型使用了 Python（因为它内置了 bignum 支持）。(n?1)Dn?2/DnDn?2 / (Dn?1 + Dn?2)

如果没有 bignum，乱序的数量和概率需要近似为double，这将产生轻微的偏差并将要乱序的数组的大小限制为大约 170 个元素。（long double允许稍微多一点。）如果限制太多，您可以使用一些 bignum 库来实现该算法。为了便于实现，我使用 Posixdrand48函数生成double范围 [0.0, 1.0) 内的随机s。这不是一个很好的随机数函数，但它可能足以达到目的，并且在大多数标准 C 库中都可用。

由于没有尝试验证要乱序的向量中元素的唯一性，具有重复元素的向量可能会产生乱序，其中一个或多个这些元素似乎位于原始位置。（它实际上是具有相同值的不同元素。）

编码：

/* Deranges the vector `arr` (of length `n`) in place, to produce
 * a permutation of the original vector where every element has
 * been moved to a new position. Returns `true` unless the derangement
 * failed because `n` was 1.
 */
bool derange(int arr[], size_t n) {
  if (n < 2) return n != 1;
  /* Compute derangement counts ("subfactorials") */
  double subfact[n];
  subfact[0] = 1;
  subfact[1] = 0;
  for (size_t i = 2; i < n; ++i)
    subfact[i] = (i - 1) * (subfact[i - 2] + subfact[i - 1]);

  /* The vector 'todo' is the stack of elements which have not yet
   * been (fully) deranged; `u` is the count of elements in the stack
   */
  size_t todo[n];
  for (size_t i = 0; i < n; ++i) todo[i] = i;
  size_t u = n;

  /* While the stack is not empty, derange the element at the
   * top of the stack with some element lower down in the stack
   */
  while (u) {
    size_t i = todo[--u];      /* Pop the stack */
    size_t j = u * drand48();  /* Get a random stack index */
    swap(arr, i, todo[j]);     /* i will follow j in its cycle */
    /* If we're generating a 2-cycle, remove the element at j */
    if (drand48() * (subfact[u - 1] + subfact[u]) < subfact[u - 1])
      todo[j] = todo[--u];
  }
  return true;
}

笔记

1. 很多人都弄错了，特别是在社交场合，比如“密友”选择（我相信这在世界其他地方有时被称为“圣诞老人游戏”。）错误的算法是如果随机选择不同的交换shuffle 产生一个固定点，除非固定点在最后，在这种情况下重新启动 shuffle。这将产生随机混乱，但选择是有偏差的，特别是对于小向量。请参阅此答案以分析偏差。

2. 即使您不使用所有整数都被视为固定大小的 RAM 模型，所使用的空间仍然与以位为单位的输入大小呈线性关系，因为 N 个不同的输入值必须至少具有 N log N 位。该算法和 MP&P 都没有尝试对具有重复元素的列表进行乱序排列，这是一个更难的问题。