在使每个索引具有与任何索引相同的概率的同时对数组进行混洗
我想改组一个数组，并且每个索引都有相同的概率在任何其他索引中（不包括它自己）。
我有这个解决方案，只有我发现总是最后2个索引总是相互交换：
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); } } 但最终可能会有一些指数再次回到第一位。
有什么想法吗？
C lang。
没有元素在其原始位置的置换（shuffle）称为紊乱 。
生成随机紊乱比生成随机排列更难，可以在线性时间和空间中完成。 （生成随机排列可以在线性时间和恒定空间中完成。）以下是两种可能的算法。
理解的最简单的解决方案是拒绝策略：做一个Fisher-Yates洗牌，但如果洗牌试图将一个元素放在其原始位置，则重新启动洗牌。 [注1]
由于随机混洗是紊乱的概率约为1 / e ，因此所执行的混洗的预期数量约为e （即，2.71828 ……）。 但是，一旦遇到第一个固定点，就会重新启动不成功的shuffle，所以shuffle步骤的总数小于数组大小的e倍进行详细分析，参见本文 ，certificate了预期的随机数需要的数量。算法大约是（ 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); }
以下function基于ConradoMartínez，Alois Panholzer和Helmut Prodinger的2008年论文“Generating Random Disrangements”，尽管我使用不同的机制来跟踪周期。 他们的算法使用大小为N的位向量，但使用拒绝策略以找到尚未标记的元素。 我的算法使用尚未操作的索引的显式向量。 矢量的大小也是N ，它仍然是O（N）空间[注2]; 因为在实际应用中， N不会很大，差异不是恕我直言的重要。 好处是选择下一个要使用的元素可以通过对随机数生成器的单次调用来完成。 同样，这并不是特别重要，因为MP＆P算法中预期的拒绝次数非常小。 但对我来说似乎更整洁。
算法的基础（MP＆P和我的）是产生紊乱的递归过程。 重要的是要注意，紊乱必然是一些循环的组成，其中每个循环的大小大于1.（大小为1的循环是固定点。）因此，可以从中构造大小为N的紊乱。使用以下两种机制之一进行较小的紊乱：
-
产生除元素
N之外的N-1元素的紊乱，并在该周期中的任何点处将N添加到某个周期。 为此，随机选择N-1循环中的任何元素j，并在j的循环中将j紧跟在j之后。 该替代方案涵盖了N在大小> 3的循环中的所有可能性。 -
产生除
N以外的N-1元素的N-2的紊乱，并添加由N组成的大小为2的循环和未从较小的紊乱中选择的元素。 该替代方案涵盖了N处于2的循环中的所有可能性。
如果D n是大小为n的紊乱数，则从上面的递归中很容易看出：
D n = (n−1)(D n−1 + D n−2 )
在两种情况下乘数都是n−1 ：在第一种选择中，它指的是可以添加N的可能位置的数量，并且在第二种替代中，选择递归紊乱的n−2元素的可能方式的数量。
因此，如果我们递归地产生大小为N的随机紊乱，我们将随机选择N-1前一个元素中的一个，然后做出一个随机布尔决定是否生成替代1或替代2，由数量加权在每种情况下可能出现紊乱。
该算法的一个优点是它可以解开任意向量; 与拒绝算法一样，不需要将置换索引应用于原始矢量。
正如MP＆P所说，递归算法可以很容易地迭代执行。 在替代方案2的情况下，这是非常清楚的，因为新的2周期可以在递归之前或之后生成，所以它也可以先完成，然后递归只是一个循环。 但对于替代方案1也是如此：即使在我们知道最终将进入哪个循环j之前，我们也可以使元素N成为循环中的后继元素j随机选择的元素j 。看这种方式，两种替代方案之间的差异减小了是否从未来的考虑中删除了元素j 。
如递归所示，替代2应该以概率(n−1)D n−2 /D n ，这是MP＆P写出他们的算法的方式。 我使用等效公式D n−2 / (D n−1 + D n−2 ) ，主要是因为我的原型使用了Python（因为它内置的bignum支持）。
没有bignums，紊乱的数量和因此概率需要近似为double ，这将产生轻微偏差并将arrays的大小限制为大约170个元素。 （ long double会允许更多。）如果这是一个太多的限制，你可以使用一些bignum库实现算法。 为了便于实现，我使用Posix drand48函数生成[ drand48 ]范围内的随机double精度数。 这不是一个很好的随机数函数，但它可能足以达到目的，并且在大多数标准C库中都可用。
由于没有尝试validation要被紊乱的向量中的元素的唯一性，因此具有重复元素的向量可能产生紊乱，其中这些元素中的一个或多个看起来在原始位置。 （它实际上是具有相同值的不同元素。）
代码：
/* 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; }
笔记
-
很多人都弄错了，特别是在社交场合，比如“秘密朋友”的选择（我相信这在世界其他地方有时被称为“圣诞老人游戏”。）不正确的算法是如果随机选择一个不同的交换shuffle产生一个固定点，除非固定点位于最后，在这种情况下重新启动shuffle。 这将产生随机紊乱，但选择是有偏见的，特别是对于小向量。 请参阅此答案以分析偏差。
-
即使您不使用其中所有整数都被视为固定大小的RAM模型，所使用的空间仍然是以位为单位的输入大小的线性，因为N个不同的输入值必须至少具有N log N位。 这个算法和MP＆P都没有尝试用重复元素来消除列表，这是一个更难的问题。
您的算法几乎是正确的（在算法中意味着意外的结果）。 由于散布的一些小错误，它不会产生预期的结果。
首先，除非N是可能值的数量的除数，否则不保证rand() % N产生均匀分布。 在任何其他情况下，你会有轻微的偏见。 无论如何，我的rand将其描述为一个坏的随机数生成器 ，所以你应该尝试使用random或如果可用的arc4random_uniform 。
但是避免索引回到原来的位置既是一致的，也很难实现。 我能想象的唯一方法是保留一个数字数组[0; n [和交换它与真实数组相同，以便能够知道数字的原始索引。
代码可能变成：
void Shuffle(int arr[]. size_t n) { int i, newIndx; int *indexes = malloc(n * sizeof(int)); for (i=0; i
注意：算法应该是正确的，但代码尚未经过测试，可能包含错别字...