随机排列数组，同时使每个索引具有相同的概率出现在任何索引中
Shuffle an array while making each index have the same probability to be in any index
我想打乱一个数组，并且每个索引都有相同的概率出现在任何其他索引（不包括它自己）中。
我有这个解决方案，只是我发现最后两个索引总是不会相互交换：
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 语言
您的算法仅几乎正确（在算法中这意味着意外结果）。由于零散的一些小错误，它不会产生预期的结果。
首先，rand() % N 不能保证产生均匀分布，除非 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<n; i++) indexes[i] = i;
for(i=0; i < n - 1; ++i) // beware to the inequality!
{
int i1;
// search if index i is in the [i; n[ current array:
for (i1=i; i1 < n; ++i) {
if (indexes[i1] == i) { // move it to i position
if (i1 != i) { // nothing to do if already at i
swap(i, i1, arr);
swap(i, i1, indexes);
}
break;
}
}
i1 = (i1 == n) ? i : i+1; // we will start the search at i1
// to guarantee that no element keep its place
newIndx = i1 + arc4random_uniform(n - i1);
/* if arc4random is not available:
newIndx = i1 + (random() % (n - i1));
*/
swap(i, newIndx, arr);
swap(i, newIndx, indexes);
}
/* special case: a permutation of [0: n-1[ have left last element in place
* we will exchange the last element with a random one
*/
if (indexes[n-1] == n-1) {
newIndx = arc4random_uniform(n-1)
swap(n-1, newIndx, arr);
swap(n-1, newIndx, indexes);
}
free(indexes); // don't forget to free what we have malloc'ed...
}
注意：算法应该是正确的，但代码未经测试，可能包含拼写错误...
没有元素在其原始位置的排列（洗牌）称为混乱。
生成随机排列比生成随机排列更难，可以在线性时间内完成 space。 （生成随机排列可以在线性时间和常数space内完成。）这里有两种可能的算法。
最容易理解的解决方案是拒绝策略：进行 Fisher-Yates 洗牌，但如果洗牌试图将元素放在其原始位置，则重新开始洗牌。 [注1]
由于随机洗牌是混乱的概率大约为 1/e，因此执行的洗牌的预期次数约为 e （即 2.71828……）。但是由于不成功的shuffle一遇到第一个固定点就重新开始，所以shuffle的总步数小于数组大小的e倍详细分析见this paper，这证明了算法所需的随机数的预期数量约为（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)space [注2]；由于在实际应用中，N 不会很大，恕我直言，差异并不显着。好处是 select 下一个要使用的元素可以通过对随机数生成器的一次调用来完成。同样，这并不是特别重要，因为 MP&P 算法中的 expected 拒绝次数非常少。但对我来说似乎更整洁。
算法（MP&P 和我的）的基础是产生紊乱的递归过程。重要的是要注意，紊乱必然是由一定数量的循环组成，其中每个循环的大小都大于 1。（大小为 1 的循环是一个不动点。）因此，大小为 N 的紊乱可以从使用以下两种机制之一的较小的紊乱：
对元素 N 以外的 N-1 元素进行排序，并在该循环的任意点将 N 添加到某个循环。为此，在 N-1 循环中随机 select 任何元素 j，并在 j 循环中将 N 紧跟在 j 之后。此替代方案涵盖了 N 处于大小 > 3 的循环中的所有可能性。
对除N以外的N-1个元素产生N-2的乱序，并添加由N和N组成的大小为2的循环该元素不是 select 从较小的混乱中编辑的。此替代方案涵盖了 N 在大小为 2 的循环中的所有可能性。
如果D<sub>n</sub>是大小为n的乱序数，从上面的递归很容易看出那：
D<sub>n</sub> = (n−1)(D<sub>n−1</sub> + D<sub>n−2</sub>)
两种情况下的乘数都是n−1：第一种选择是指可以相加的可能的地方数N，第二种选择是指可能的路数到selectn−2个递归错乱的元素。
因此，如果我们要递归地产生大小为 N 的随机紊乱，我们将随机 select 前面的 N-1 个元素之一，然后进行随机布尔决策关于是否产生备选方案 1 或备选方案 2，由每种情况下可能的紊乱数量加权。
这个算法的一个优点是它可以打乱任意向量；不需要像拒绝算法那样将置换索引应用于原始向量。
正如 MP&P 所指出的，递归算法可以很容易地迭代执行。这在备选方案 2 的情况下非常清楚，因为新的 2 循环可以在递归之前或之后生成，所以最好先完成，然后递归只是一个循环。但这对于备选方案 1 也是如此：我们可以使元素 N 成为随机 select 元素 j 的循环中的后继者，甚至在我们知道哪个循环 j 之前最终会出现。这样看来，两个备选方案之间的区别就在于是否将元素 j 从未来的考虑中移除。
如递归所示，选择方案 2 的概率为 (n−1)D<sub>n−2</sub>/D<sub>n </sub>，这就是 MP&P 编写算法的方式。我使用了等效公式 D<sub>n−2</sub> / (D<sub>n−1</sub> + D<sub>n−2 </sub>)，主要是因为我的原型使用了 Python（因为它内置了 bignum 支持）。
没有 bignums，紊乱的数量和概率需要近似为 double，这将产生轻微的偏差并将要紊乱的数组的大小限制为大约 170 个元素。 （long double 允许稍微多一些。）如果限制太多，您可以使用一些 bignum 库来实现该算法。为了便于实现，我使用 Posix drand48 函数在 [0.0, 1.0) 范围内生成随机 doubles。这不是一个很好的随机数函数，但它可能足以满足目的并且在大多数标准 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;
}
备注
很多人都弄错了，尤其是在社交场合，例如“秘密朋友”selection（我相信这在世界其他地方有时被称为“圣诞老人游戏” .) 不正确的算法是，如果随机洗牌产生固定点，则只选择不同的交换，除非固定点在最后，在这种情况下重新开始洗牌。这将产生随机紊乱，但 selection 是有偏差的，特别是对于小向量。有关偏差的分析，请参阅 。
即使您不使用所有整数都被认为是固定大小的 RAM 模型，所使用的 space 仍然与以位为单位的输入大小成线性关系，因为 N distinct 输入值必须至少有 N log N 位。该算法和 MP&P 都没有尝试对包含重复元素的列表进行排序，这是一个更难的问题。
我想打乱一个数组，并且每个索引都有相同的概率出现在任何其他索引（不包括它自己）中。
我有这个解决方案，只是我发现最后两个索引总是不会相互交换：
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 语言
您的算法仅几乎正确（在算法中这意味着意外结果）。由于零散的一些小错误，它不会产生预期的结果。
首先，rand() % N 不能保证产生均匀分布，除非 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<n; i++) indexes[i] = i;
for(i=0; i < n - 1; ++i) // beware to the inequality!
{
int i1;
// search if index i is in the [i; n[ current array:
for (i1=i; i1 < n; ++i) {
if (indexes[i1] == i) { // move it to i position
if (i1 != i) { // nothing to do if already at i
swap(i, i1, arr);
swap(i, i1, indexes);
}
break;
}
}
i1 = (i1 == n) ? i : i+1; // we will start the search at i1
// to guarantee that no element keep its place
newIndx = i1 + arc4random_uniform(n - i1);
/* if arc4random is not available:
newIndx = i1 + (random() % (n - i1));
*/
swap(i, newIndx, arr);
swap(i, newIndx, indexes);
}
/* special case: a permutation of [0: n-1[ have left last element in place
* we will exchange the last element with a random one
*/
if (indexes[n-1] == n-1) {
newIndx = arc4random_uniform(n-1)
swap(n-1, newIndx, arr);
swap(n-1, newIndx, indexes);
}
free(indexes); // don't forget to free what we have malloc'ed...
}
注意：算法应该是正确的，但代码未经测试，可能包含拼写错误...
没有元素在其原始位置的排列（洗牌）称为混乱。
生成随机排列比生成随机排列更难，可以在线性时间内完成 space。 （生成随机排列可以在线性时间和常数space内完成。）这里有两种可能的算法。
最容易理解的解决方案是拒绝策略：进行 Fisher-Yates 洗牌，但如果洗牌试图将元素放在其原始位置，则重新开始洗牌。 [注1]
由于随机洗牌是混乱的概率大约为 1/e，因此执行的洗牌的预期次数约为 e （即 2.71828……）。但是由于不成功的shuffle一遇到第一个固定点就重新开始，所以shuffle的总步数小于数组大小的e倍详细分析见this paper，这证明了算法所需的随机数的预期数量约为（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)space [注2]；由于在实际应用中，N 不会很大，恕我直言，差异并不显着。好处是 select 下一个要使用的元素可以通过对随机数生成器的一次调用来完成。同样，这并不是特别重要，因为 MP&P 算法中的 expected 拒绝次数非常少。但对我来说似乎更整洁。
算法（MP&P 和我的）的基础是产生紊乱的递归过程。重要的是要注意，紊乱必然是由一定数量的循环组成，其中每个循环的大小都大于 1。（大小为 1 的循环是一个不动点。）因此，大小为 N 的紊乱可以从使用以下两种机制之一的较小的紊乱：
对元素
N以外的N-1元素进行排序，并在该循环的任意点将N添加到某个循环。为此，在N-1循环中随机 select 任何元素j，并在j循环中将N紧跟在j之后。此替代方案涵盖了N处于大小 > 3 的循环中的所有可能性。对除
N以外的N-1个元素产生N-2的乱序，并添加由N和N组成的大小为2的循环该元素不是 select 从较小的混乱中编辑的。此替代方案涵盖了N在大小为 2 的循环中的所有可能性。
如果D<sub>n</sub>是大小为n的乱序数，从上面的递归很容易看出那：
D<sub>n</sub> = (n−1)(D<sub>n−1</sub> + D<sub>n−2</sub>)
两种情况下的乘数都是n−1：第一种选择是指可以相加的可能的地方数N，第二种选择是指可能的路数到selectn−2个递归错乱的元素。
因此，如果我们要递归地产生大小为 N 的随机紊乱，我们将随机 select 前面的 N-1 个元素之一，然后进行随机布尔决策关于是否产生备选方案 1 或备选方案 2，由每种情况下可能的紊乱数量加权。
这个算法的一个优点是它可以打乱任意向量；不需要像拒绝算法那样将置换索引应用于原始向量。
正如 MP&P 所指出的，递归算法可以很容易地迭代执行。这在备选方案 2 的情况下非常清楚，因为新的 2 循环可以在递归之前或之后生成，所以最好先完成，然后递归只是一个循环。但这对于备选方案 1 也是如此：我们可以使元素 N 成为随机 select 元素 j 的循环中的后继者，甚至在我们知道哪个循环 j 之前最终会出现。这样看来，两个备选方案之间的区别就在于是否将元素 j 从未来的考虑中移除。
如递归所示，选择方案 2 的概率为 (n−1)D<sub>n−2</sub>/D<sub>n </sub>，这就是 MP&P 编写算法的方式。我使用了等效公式 D<sub>n−2</sub> / (D<sub>n−1</sub> + D<sub>n−2 </sub>)，主要是因为我的原型使用了 Python（因为它内置了 bignum 支持）。
没有 bignums，紊乱的数量和概率需要近似为 double，这将产生轻微的偏差并将要紊乱的数组的大小限制为大约 170 个元素。 （long double 允许稍微多一些。）如果限制太多，您可以使用一些 bignum 库来实现该算法。为了便于实现，我使用 Posix drand48 函数在 [0.0, 1.0) 范围内生成随机 doubles。这不是一个很好的随机数函数，但它可能足以满足目的并且在大多数标准 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;
}
备注
很多人都弄错了，尤其是在社交场合，例如“秘密朋友”selection（我相信这在世界其他地方有时被称为“圣诞老人游戏” .) 不正确的算法是，如果随机洗牌产生固定点，则只选择不同的交换，除非固定点在最后，在这种情况下重新开始洗牌。这将产生随机紊乱，但 selection 是有偏差的，特别是对于小向量。有关偏差的分析，请参阅
即使您不使用所有整数都被认为是固定大小的 RAM 模型，所使用的 space 仍然与以位为单位的输入大小成线性关系，因为 N distinct 输入值必须至少有 N log N 位。该算法和 MP&P 都没有尝试对包含重复元素的列表进行排序，这是一个更难的问题。