这个问题在微软面试中被问到过。非常想知道为什么这些人会问这么奇怪的概率问题？
给定一个 rand(N)，一个随机生成器，它生成从 0 到 N-1 的随机数。
int A[N]; // An array of size N
for(i = 0; i < N; i++)
{
int m = rand(N);
int n = rand(N);
swap(A[m],A[n]);
}
编辑：请注意，种子不是固定的。
数组 A 保持不变的概率是多少？
假设数组包含唯一元素。
好吧，我对这个有一点乐趣。当我第一次阅读这个问题时，我首先想到的是群论（特别是对称群 S n）。for 循环通过在每次迭代中组合转置（即交换）来简单地在 S n中构建置换 σ 。我的数学并没有那么出色，而且我有点生疏，所以如果我的符号不合适，请忍耐。
假设A我们的数组在排列后不变。我们最终被要求找到事件的概率A，Pr(A)。
我的解决方案尝试遵循以下过程：
请注意，for 循环的每次迭代都会创建一个交换（或转置），它会导致以下两种情况之一（但绝不会同时出现两种情况）：
我们标记第二种情况。让我们定义一个恒等转置如下：
当一个数字与自身交换时，就会发生身份转置。也就是说，当 n == m 在上面的 for 循环中时。
对于列出的代码的任何给定运行，我们组合N转置。在这个“链”中可能会0, 1, 2, ... , N出现身份换位。
例如，考虑一个N = 3案例：
Given our input [0, 1, 2].
Swap (0 1) and get [1, 0, 2].
Swap (1 1) and get [1, 0, 2]. ** Here is an identity **
Swap (2 2) and get [1, 0, 2]. ** And another **
请注意，有奇数个非恒等转置 (1) 并且数组已更改。
假设K_i身份i转置出现在给定的排列中。请注意，这形成了所有可能结果的详尽划分：
0和Nidentity 换位。因此我们可以应用全概率定律：
现在我们终于可以利用分区了。请注意，当非恒等转置的数量为奇数时，数组不可能保持不变*。因此：
*根据群论，排列是偶数或奇数，但绝不是两者兼而有之。因此奇排列不能是恒等排列（因为恒等排列是偶排列）。
所以我们现在必须确定两个N-i偶数概率：
第一项 ,表示获得具有i恒等转置的排列的概率。事实证明这是二项式的，因为对于 for 循环的每次迭代：
1/N。因此，对于N试验，获得i同一性转置的概率为：
因此，如果您已经做到了这一点，我们已经将问题减少到寻找偶数N - i。i这表示在给定转置是身份的情况下获得身份置换的概率。我使用一种简单的计数方法来确定在可能的排列数量上实现恒等排列的方法的数量。
首先考虑排列(n, m)和(m, n)等价。然后，让M是可能的非恒等排列的数量。我们会经常使用这个数量。
这里的目标是确定可以组合转置集合以形成恒等排列的方式的数量。我将尝试构建一个通用的解决方案N = 4。
让我们考虑N = 4所有身份转置（ie i = N = 4）的情况。让我们X表示一个身份转置。对于每个X，都有N可能（它们是：n = m = 0, 1, 2, ... , N - 1）。因此存在N^i = 4^4实现身份置换的可能性。为了完整起见，我们添加了二项式系数 ，C(N, i)以考虑恒等转置的排序（这里它仅等于 1）。我试图用上面元素的物理布局和下面的可能性数量来描述这个：
I = _X_ _X_ _X_ _X_
N * N * N * N * C(4, 4) => N^N * C(N, N) possibilities
现在没有明确地替换N = 4and i = 4，我们可以看一下一般情况。将上述内容与之前找到的分母相结合，我们发现：
这是直观的。事实上，除此之外的任何其他值1都可能会引起您的警觉。想一想：我们处于这样一种情况，在这种情况下，所有的N换位都被称为同一性。在这种情况下，数组可能没有变化？很明显，1.
现在，再次为N = 4，让我们考虑 2 个单位换位（ie i = N - 2 = 2）。作为约定，我们将把这两个身份放在最后（并考虑稍后的排序）。我们现在知道我们需要选择两个转置，当它们组合时，它们将成为恒等排列。让我们将任何元素放在第一个位置，称之为t1。如上所述，有M可能假设t1不是一个身份（它不可能是因为我们已经放置了两个）。
I = _t1_ ___ _X_ _X_
M * ? * N * N
剩下的唯一可能出现在第二个位置的元素是 的逆t1，实际上是t1（这是唯一的逆唯一性）。我们再次包括二项式系数：在这种情况下，我们有 4 个开放位置，我们正在寻找放置 2 个身份排列。我们有多少种方法可以做到这一点？4选2。
I = _t1_ _t1_ _X_ _X_
M * 1 * N * N * C(4, 2) => C(N, N-2) * M * N^(N-2) possibilities
再看一般情况，这都对应于：
最后我们做N = 4没有身份转置的情况（ie i = N - 4 = 0）。由于有很多可能性，它开始变得棘手，我们必须小心不要重复计算。我们以类似的方式开始，在第一个位置放置一个元素并计算出可能的组合。先取最简单的：相同的换位4次。
I = _t1_ _t1_ _t1_ _t1_
M * 1 * 1 * 1 => M possibilities
现在让我们考虑两个独特的元素t1和t2。(因为不能等于)有并且只有M可能。如果我们用尽所有安排，我们将得到以下模式：t1M-1t2t2t1
I = _t1_ _t1_ _t2_ _t2_
M * 1 * M-1 * 1 => M * (M - 1) possibilities (1)st
= _t1_ _t2_ _t1_ _t2_
M * M-1 * 1 * 1 => M * (M - 1) possibilities (2)nd
= _t1_ _t2_ _t2_ _t1_
M * M-1 * 1 * 1 => M * (M - 1) possibilities (3)rd
现在让我们考虑三个独特的元素t1, t2, t3。让我们t1先放置然后再放置t2。像往常一样，我们有：
I = _t1_ _t2_ ___ ___
M * ? * ? * ?
我们还不能说有多少可能t2的 s，我们马上就会知道为什么。
我们现在排t1在第三位。注意，t1必须去那里，因为如果要在最后一个地方去，我们只会重新创建(3)rd上面的安排。重复计算是不好的！这将第三个唯一元素留t3到最终位置。
I = _t1_ _t2_ _t1_ _t3_
M * ? * 1 * ?
那么为什么我们要花一分钟时间来t2更仔细地考虑 s 的数量呢？转置t1和t2 不能是不相交的排列（即它们必须共享一个（并且只有一个，因为它们也不能相等）它们的nor m）。这样做的原因是因为如果它们不相交，我们可以交换排列的顺序。这意味着我们将重复计算(1)st安排。
说t1 = (n, m)。t2必须是形式(n, x)或(y, m)对某些人来说x，并且y为了不脱节。请注意，x可能不是norm并且y很多不是nor m。因此，可能的排列数t2实际上是2 * (N - 2)。
所以，回到我们的布局：
I = _t1_ _t2_ _t1_ _t3_
M * 2(N-2) * 1 * ?
现在t3必须是 的组合的倒数t1 t2 t1。让我们手动完成：
(n, m)(n, x)(n, m) = (m, x)
因此t3必须是(m, x)。请注意，这与任何一个都不相交t1也不等于，t1因此t2这种情况下没有重复计算。
I = _t1_ _t2_ _t1_ _t3_
M * 2(N-2) * 1 * 1 => M * 2(N - 2) possibilities
最后，将所有这些放在一起：
就是这样了。向后工作，将我们发现的内容代入步骤 2 中给出的原始总和。我计算了N = 4以下案例的答案。它与另一个答案中的经验数字非常接近！
N = 4
M = 6 _________ _____________ _________
| Pr(K_i) | Pr(A | K_i) | 产品 |
_________|_________|_____________|_________|
| | | | |
| 我 = 0 | 0.316 | 120 / 1296 | 0.029 |
|_________|_________|_____________|_________|
| | | | |
| 我 = 2 | 0.211 | 6 / 36 | 0.035 |
|_________|_________|_____________|_________|
| | | | |
| 我 = 4 | 0.004 | 1 / 1 | 0.004 |
|_________|_________|_____________|_________|
| | |
| 总和：| 0.068 |
|_____________|_________|
如果能在这里应用群论的结果，那就太酷了——也许有！它肯定会帮助让所有这些繁琐的计数完全消失（并将问题简化为更优雅的东西）。我停止在N = 4. 对于N > 5，给出的只是一个近似值（有多好，我不确定）。如果您考虑一下，就会很清楚为什么会这样：例如，给定换位，显然有多种方法可以使用上面未说明的四个独特元素来N = 8创建身份。随着排列变长（据我所知......），方式的数量似乎变得越来越难以计数。
无论如何，我绝对不能在采访的范围内做这样的事情。如果我幸运的话，我会走到分母一步。除此之外，它似乎非常讨厌。
非常想知道为什么这些人会问这么奇怪的概率问题？
提出这样的问题是因为它们可以让面试官深入了解受访者的
... 等等。提出暴露受访者这些属性的问题的关键是要有一段看似简单的代码。这摆脱了非编码员被卡住的冒名顶替者；傲慢的人跳到错误的结论；懒惰或低于标准的计算机科学家找到了一个简单的解决方案并停止寻找。通常，正如他们所说，重要的不是你是否得到了正确的答案，而是你是否对自己的思维过程印象深刻。
我也会尝试回答这个问题。在一次采访中，我会解释自己而不是提供单行的书面答案——这是因为即使我的“答案”是错误的，我也能够展示出逻辑思维。
A 将保持不变 - 即相同位置的元素 - 当
m == n在每次迭代中（以便每个元素只与自身交换）；或者第一种情况是duedl0r 给出的“简单”情况，即数组未更改的情况。这可能是答案，因为
数组 A 保持不变的概率是多少？
如果数组在 处更改，i = 1然后在 处恢复i = 2，则它处于原始状态，但没有“保持不变” - 它已更改，然后又更改回。这可能是一个聪明的技术。
然后考虑元素被交换和交换回来的机会——我认为在采访中计算超出了我的头脑。显而易见的考虑是，这不需要进行更改 - 更改回交换，可以很容易地在三个元素之间进行交换，交换 1 和 2，然后交换 2 和 3，交换 1 和 3，最后交换 2 和 3。继续，可能会有 4、5 个或更多像这样的“圆形”项目之间的交换。
事实上，与其考虑数组不变的情况，考虑改变的情况可能更简单。考虑这个问题是否可以映射到像帕斯卡三角形这样的已知结构上。
这是一个难题。我同意在面试中很难解决，但这并不意味着在面试中提问太难。差的候选人不会有答案，一般的候选人会猜出明显的答案，而优秀的候选人会解释为什么这个问题太难回答了。
我认为这是一个“开放式”问题，可以让面试官深入了解候选人。出于这个原因，即使在面试中很难解决，但在面试中问这个问题是个好问题。提出问题不仅仅是检查答案是对还是错。
下面是 C 代码，用于计算 rand 可以产生的 2N 个索引元组的值的数量并计算概率。从 N = 0 开始，它显示计数为 1、1、8、135、4480、189125 和 12450816，概率为 1、1、0.5、0.185185、0.0683594、0.0193664 和 0.00571983。计数没有出现在Encyclopedia of Integer Sequences中，所以要么我的程序有错误，要么这是一个非常模糊的问题。如果是这样，这个问题并不是要由求职者解决，而是要暴露他们的一些思维过程以及他们如何处理挫折。我不会认为这是一个很好的面试问题。
#include <inttypes.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define swap(a, b) do { int t = (a); (a) = (b); (b) = t; } while (0)
static uint64_t count(int n)
{
// Initialize count of how many times the original order is the result.
uint64_t c = 0;
// Allocate space for selectors and initialize them to zero.
int *r = calloc(2*n, sizeof *r);
// Allocate space for array to be swapped.
int *A = malloc(n * sizeof *A);
if (!A || !r)
{
fprintf(stderr, "Out of memory.\n");
exit(EXIT_FAILURE);
}
// Iterate through all values of selectors.
while (1)
{
// Initialize A to show original order.
for (int i = 0; i < n; ++i)
A[i] = i;
// Test current selector values by executing the swap sequence.
for (int i = 0; i < 2*n; i += 2)
{
int m = r[i+0];
int n = r[i+1];
swap(A[m], A[n]);
}
// If array is in original order, increment counter.
++c; // Assume all elements are in place.
for (int i = 0; i < n; ++i)
if (A[i] != i)
{
// If any element is out of place, cancel assumption and exit.
--c;
break;
}
// Increment the selectors, odometer style.
int i;
for (i = 0; i < 2*n; ++i)
// Stop when a selector increases without wrapping.
if (++r[i] < n)
break;
else
// Wrap this selector to zero and continue.
r[i] = 0;
// Exit the routine when the last selector wraps.
if (2*n <= i)
{
free(A);
free(r);
return c;
}
}
}
int main(void)
{
for (int n = 0; n < 7; ++n)
{
uint64_t c = count(n);
printf("N = %d: %" PRId64 " times, %g probabilty.\n",
n, c, c/pow(n, 2*n));
}
return 0;
}
数组的N个元素A可以排列成N ! 不同的排列。让我们从 1 到N !对这些排列进行编号，例如按字典顺序。所以算法中任意时刻数组的状态A都可以完全用置换数来表征。
例如，对于N = 3，所有 3 中的一个可能编号！= 6 个排列可能是：
在算法的每一步中，状态A要么保持不变，要么从这些排列中的一个转换到另一个。我们现在对这些状态变化的概率感兴趣。让我们称Pr( i → j )在单次循环迭代中状态从排列i变为排列j的概率。
当我们从 [0, N -1]范围内统一且独立地选择m和n时，有N ² 种可能的结果，其中每一个的可能性都相同。
对于这些结果中的N个， m = n成立，因此排列没有变化。所以，
.
剩下的N ² - N个情况是转置，即两个元素交换它们的位置，因此排列发生了变化。假设这些转置之一交换位置x和y的元素。算法如何生成这种转置有两种情况：m = x , n = y或m = y , n = x。因此，每个转置的概率为 2 / N ²。
这与我们的排列有什么关系？当且仅当存在将i转换为j的转置（反之亦然）时，我们称两个排列i和j为 邻居。那么我们可以得出结论：
我们可以将概率 Pr( i → j ) 排列在转移矩阵P ∈ [0,1] N !× N中！. 我们定义
p ij = Pr( i → j ),
其中p ij是P的第i行第j列中的条目。注意
Pr( i → j ) = Pr( j → i )，
这意味着P是对称的。
现在的关键点是观察当我们将P自身相乘时会发生什么。取P ²的任何元素p (2) ij ：
乘积 Pr( i → k ) · Pr( k → j ) 是从排列i开始我们一步转换到排列k并在另一个后续步骤后转换到排列j的概率。因此，对所有中间排列k求和给出了在 2 个步骤中从i转换到j的总概率。
这个论点可以扩展到P的更高次幂。一个特殊的后果如下：
p ( N ) ii是在N步后返回到排列i的概率，假设我们从排列i开始。
让我们用N = 3 来解决这个问题。我们已经有了排列的编号。对应的转移矩阵如下：
将P与自身相乘得到：
另一个乘法产生：
主对角线的任何元素都会给我们想要的概率，即15 / 81或5 / 27。
虽然这种方法在数学上是合理的并且可以应用于N的任何值，但这种形式并不是很实用。转换矩阵P有N !² 个条目，它变得非常快。即使对于N = 10，矩阵的大小也已经超过 13 万亿个条目。因此，这种算法的简单实现似乎是不可行的。
然而，与其他提议相比，这种方法非常结构化，除了找出哪些排列是邻居之外，不需要复杂的推导。我希望可以利用这种结构化来找到更简单的计算。
例如，可以利用P的任何幂的所有对角元素都相等这一事实。假设我们可以很容易地计算出P N的轨迹，那么解决方案就是 tr( P N ) / N !。P N的迹等于其特征值的N次方之和。因此，如果我们有一个有效的算法来计算P的特征值，我们就会被设置。然而，除了计算N = 5 的特征值之外，我还没有进一步探索这一点。
很容易观察到界限 1/n n <= p <= 1/n。
这是显示反指数上限的不完整想法。
您正在从 {1,2,..,n} 中抽取 2n 次数字。如果其中任何一个是唯一的（仅出现一次），则数组肯定会更改，因为元素已经消失并且无法返回其原始位置。
一个固定数唯一的概率是 2n * 1/n * (1-1/n)^(2n-1)=2 * (1-1/n)^(2n-1) 是渐近的 2/e 2，从 0 开始。 [2n 因为您选择在哪个尝试中获得它， 1/n 表示您在该尝试中获得它， (1-1/n)^(2n-1) 表示您没有获得它其他尝试]
如果事件是独立的，那么所有数字都不唯一的机会是 (2/e 2 )^n，这意味着 p <= O((2/e 2 )^n)。不幸的是，它们不是独立的。我觉得可以通过更复杂的分析来显示界限。关键字是“球和垃圾箱问题”。
一个简单的解决方案是
p >= 1 / N N
由于数组保持不变的一种可能方式是m = n每次迭代。并且m等于n可能性1 / N。
肯定比那个高。问题是多少..
第二个想法：人们也可以争辩说，如果你随机打乱一个数组，每个排列都有相等的概率。由于存在n!排列，因此只得到一个（我们一开始就有的）的概率是
p = 1 / N！
这比之前的结果要好一些。
正如所讨论的，该算法是有偏见的。这意味着并非每个排列都具有相同的概率。所以1 / N!不是很准确。您必须找出排列的分布情况。
仅供参考，不确定上述界限 (1/n^2) 是否成立：
N=5 -> 0.019648 < 1/25
N=6 -> 0.005716 < 1/36
采样代码：
import random
def sample(times,n):
count = 0;
for i in range(times):
count += p(n)
return count*1.0/times;
def p(n):
perm = range(n);
for i in range(n):
a = random.randrange(n)
b = random.randrange(n)
perm[a],perm[b]=perm[b],perm[a];
return perm==range(n)
print sample(500000,5)
每个人都假设A[i] == i，这没有明确说明。我也会做这个假设，但请注意概率取决于内容。例如，如果A[i]=0，则所有 N 的概率 = 1。
这是如何做到的。令P(n,i)结果数组与原始数组正好相差 i 个转置的概率。
我们想知道P(n,0)。确实如此：
P(n,0) =
1/n * P(n-1,0) + 1/n^2 * P(n-1,1) =
1/n * P(n-1,0) + 1/n^2 * (1-1/(n-1)) * P(n-2,0)
解释：我们可以通过两种方式获得原始数组，或者通过在已经好的数组中进行“中性”转置，或者通过恢复唯一的“坏”转置。为了得到一个只有一个“坏”转置的数组，我们可以取一个有 0 个坏转置的数组，并制作一个非中性的转置。
编辑： P(n-1,0) 中的 -2 而不是 -1
我会将问题建模为一个多重图，其中节点是数组的元素，而交换是在它们之间添加一个无向（！）连接。然后以某种方式寻找循环（所有节点都是循环的一部分=>原始）
真的需要回去工作了！:(
有趣的问题。
我认为答案是 1/N，但我没有任何证据。当我找到证据时，我将编辑我的答案。
到目前为止我得到了什么：
如果 m == n，则不会更改数组。得到 m == n 的概率是 1/N，因为有 N^2 个选项，并且只有 N 是合适的（(i,i) for each 0 <= i <= N-1）。
因此，我们得到 N/N^2 = 1/N。
Pk 表示在 k 次交换迭代之后，大小为 N 的数组将保持不变的概率。
P1 = 1/N。（正如我们在下面看到的）
P2 = (1/N) P1 + (N-1/N) (2/N^2) = 1/N^2 + 2(N-1) / N^3。
Explanation for P2:
We want to calculate the probability that after 2 iterations, the array with
N elements won't change. We have 2 options :
- in the 2 iteration we got m == n (Probability of 1/N)
- in the 2 iteration we got m != n (Probability of N-1/N)
If m == n, we need that the array will remain after the 1 iteration = P1.
If m != n, we need that in the 1 iteration to choose the same n and m
(order is not important). So we get 2/N^2.
Because those events are independent we get - P2 = (1/N)*P1 + (N-1/N)*(2/N^2).
Pk = (1/N)*Pk-1 + (N-1/N)*X。（第一个代表 m == n，第二个代表 m != n）
我必须更多地考虑 X 等于什么。（X 只是真实公式的替代品，不是常数或其他任何东西）
Example for N = 2.
All possible swaps:
(1 1 | 1 1),(1 1 | 1 2),(1 1 | 2 1),(1 1 | 2 2),(1 2 | 1 1),(1 2 | 1 2)
(1 2 | 2 1),(1 2 | 2 2),(2 1 | 1 1),(2 1 | 1 2),(2 1 | 2 1),(2 1 | 2 2)
(2 2 | 1 1),(2 2 | 1 2),(2 2 | 2 1),(2 1 | 1 1).
Total = 16. Exactly 8 of them remain the array the same.
Thus, for N = 2, the answer is 1/2.
编辑： 我想介绍另一种方法：
我们可以将互换分为三组：建设性互换、破坏性互换和无害互换。
建设性交换被定义为导致至少一个元素移动到正确位置的交换。
破坏性交换被定义为导致至少一个元素从其正确位置移动的交换。
无害交换被定义为不属于其他组的交换。
很容易看出这是所有可能交换的分区。（交集 = 空集）。
现在我要证明的主张：
The array will remain the same if and only if
the number of Destructive swap == Constructive swap in the iterations.
如果有人有反例，请写下来作为评论。
如果这个说法是正确的，我们可以对所有组合求和——0 个无害掉期，1 个无害掉期，..，N 个无害掉期。
对于每一个可能的 k 无害交换，我们检查 Nk 是否是偶数，如果不是，我们跳过。如果是，我们将 (Nk)/2 视为破坏性，将 (Nk) 视为建设性。看看所有的可能性。
这不是一个完整的解决方案，但至少它是一些东西。
采取一组没有效果的特定交换。我们知道，一定是它的交换最终形成了一堆不同大小的循环，总共使用了n交换。（为此，没有效果的交换可以被认为是大小为 1 的循环）
也许我们可以
1）根据循环的大小将它们分成组
2）计算获得每个组的方法数。
（主要问题是有很多不同的组，但如果不考虑不同的分组，我不确定你如何实际计算这个。）
C# 中的幼稚实现。这个想法是创建初始数组的所有可能排列并枚举它们。然后我们建立一个可能的状态变化矩阵。将矩阵与自身相乘 N 次，我们将得到矩阵，该矩阵显示在 N 步中从排列#i 到排列#j 存在多少种方式。Elemet [0,0] 将显示有多少种方式会导致相同的初始状态。第 0 行的元素总和将显示不同方式的总数。通过将前者除以后者，我们得到概率。
事实上，排列的总数是 N^(2N)。
Output:
For N=1 probability is 1 (1 / 1)
For N=2 probability is 0.5 (8 / 16)
For N=3 probability is 0.1851851851851851851851851852 (135 / 729)
For N=4 probability is 0.068359375 (4480 / 65536)
For N=5 probability is 0.0193664 (189125 / 9765625)
For N=6 probability is 0.0057198259072973293366526105 (12450816 / 2176782336)
class Program
{
static void Main(string[] args)
{
for (int i = 1; i < 7; i++)
{
MainClass mc = new MainClass(i);
mc.Run();
}
}
}
class MainClass
{
int N;
int M;
List<int> comb;
List<int> lastItemIdx;
public List<List<int>> combinations;
int[,] matrix;
public MainClass(int n)
{
N = n;
comb = new List<int>();
lastItemIdx = new List<int>();
for (int i = 0; i < n; i++)
{
comb.Add(-1);
lastItemIdx.Add(-1);
}
combinations = new List<List<int>>();
}
public void Run()
{
GenerateAllCombinations();
GenerateMatrix();
int[,] m2 = matrix;
for (int i = 0; i < N - 1; i++)
{
m2 = Multiply(m2, matrix);
}
decimal same = m2[0, 0];
decimal total = 0;
for (int i = 0; i < M; i++)
{
total += m2[0, i];
}
Console.WriteLine("For N={0} probability is {1} ({2} / {3})", N, same / total, same, total);
}
private int[,] Multiply(int[,] m2, int[,] m1)
{
int[,] ret = new int[M, M];
for (int ii = 0; ii < M; ii++)
{
for (int jj = 0; jj < M; jj++)
{
int sum = 0;
for (int k = 0; k < M; k++)
{
sum += m2[ii, k] * m1[k, jj];
}
ret[ii, jj] = sum;
}
}
return ret;
}
private void GenerateMatrix()
{
M = combinations.Count;
matrix = new int[M, M];
for (int i = 0; i < M; i++)
{
matrix[i, i] = N;
for (int j = i + 1; j < M; j++)
{
if (2 == Difference(i, j))
{
matrix[i, j] = 2;
matrix[j, i] = 2;
}
else
{
matrix[i, j] = 0;
}
}
}
}
private int Difference(int x, int y)
{
int ret = 0;
for (int i = 0; i < N; i++)
{
if (combinations[x][i] != combinations[y][i])
{
ret++;
}
if (ret > 2)
{
return int.MaxValue;
}
}
return ret;
}
private void GenerateAllCombinations()
{
int placeAt = 0;
bool doRun = true;
while (doRun)
{
doRun = false;
bool created = false;
for (int i = placeAt; i < N; i++)
{
for (int j = lastItemIdx[i] + 1; j < N; j++)
{
lastItemIdx[i] = j; // remember the test
if (comb.Contains(j))
{
continue; // tail items should be nulled && their lastItemIdx set to -1
}
// success
placeAt = i;
comb[i] = j;
created = true;
break;
}
if (comb[i] == -1)
{
created = false;
break;
}
}
if (created)
{
combinations.Add(new List<int>(comb));
}
// rollback
bool canGenerate = false;
for (int k = placeAt + 1; k < N; k++)
{
lastItemIdx[k] = -1;
}
for (int k = placeAt; k >= 0; k--)
{
placeAt = k;
comb[k] = -1;
if (lastItemIdx[k] == N - 1)
{
lastItemIdx[k] = -1;
continue;
}
canGenerate = true;
break;
}
doRun = canGenerate;
}
}
}
好吧，从数学的角度来看：
为了让数组元素每次都在同一个位置交换，那么 Rand(N) 函数必须为 int m 和 int n 生成两次相同的数字。所以 Rand(N) 函数两次生成相同数字的概率是 1/N。我们在 for 循环中调用了 N 次 Rand(N)，所以我们有 1/(N^2) 的概率
问题：数组 A 保持不变的概率是多少？条件：假设数组包含唯一元素。
尝试了 Java 中的解决方案。
随机交换发生在原始 int 数组上。在 java 方法中，参数总是按值传递，所以在 swap 方法中发生的事情并不重要，因为数组的 a[m] 和 a[n] 元素（来自下面的代码 swap(a[m], a[n]) ）是通过不完整的数组。
答案是数组将保持不变。尽管有上述情况。请参见下面的 java 代码示例：
import java.util.Random;
public class ArrayTrick {
int a[] = new int[10];
Random random = new Random();
public void swap(int i, int j) {
int temp = i;
i = j;
j = temp;
}
public void fillArray() {
System.out.println("Filling array: ");
for (int index = 0; index < a.length; index++) {
a[index] = random.nextInt(a.length);
}
}
public void swapArray() {
System.out.println("Swapping array: ");
for (int index = 0; index < a.length; index++) {
int m = random.nextInt(a.length);
int n = random.nextInt(a.length);
swap(a[m], a[n]);
}
}
public void printArray() {
System.out.println("Printing array: ");
for (int index = 0; index < a.length; index++) {
System.out.print(" " + a[index]);
}
System.out.println();
}
public static void main(String[] args) {
ArrayTrick at = new ArrayTrick();
at.fillArray();
at.printArray();
at.swapArray();
at.printArray();
}
}
样本输出：
填充数组：打印数组：3 1 1 4 9 7 9 5 9 5 交换数组：打印数组：3 1 1 4 9 7 9 5 9 5
每次迭代中 m==n 的概率，然后执行 N 次。P(m==n) = 1/N。所以我认为这种情况下 P=1/(n^2) 。但是随后您必须考虑将值交换回来。所以我认为答案是（文本编辑器让我）1/N^N。