arrays保持不变的概率是多less？

这个问题已经在微软采访中被问到。 非常好奇，为什么这些人会问这样奇怪的概率？

给定一个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保持不变的概率是多less？
假定数组包含唯一的元素。

Answer 1

_{好吧，我有一个这个有点乐趣。 我第一次读到这个问题时首先想到的是群论（特别是对称群S n ）。 for循环通过在每次迭代中组合转置（即交换），简单地在S n中build立置换σ。 我的math不是那么壮观，而且我有些生疏，所以如果我的记谱不在我身上。}

---

概观

设A是排列后我们的数组不变的事件。 我们最终被要求找出事件A ， Pr(A)的概率。

我的解决scheme尝试遵循以下过程：

1. 考虑所有可能的排列（即我们数组的重新sorting）
2. 根据它们包含的所谓的身份换位的数量将这些置换划分成不相交的集合。 这有助于减less问题， 甚至只是排列。
3. 确定置换是偶数（和特定长度）的情况下获得身份置换的概率。
4. 求和这些概率以获得arrays不变的整体概率。

1）可能的结果

请注意，for循环的每次迭代都会创build一个交换（或换位 ），从而导致以下两种情况之一（但不会同时发生）：

1. 两个元素交换。
2. 一个元素与自己交换。 为了我们的意图和目的，arrays不变。

我们标注第二个案例。 我们来定义一个身份转换 ，如下所示：

数字与自身交换时，会发生身份转换 。 也就是说，当在上面for循环n == m。

对于任何给定的代码运行，我们组成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），并且数组已更改。

---

2）基于身份转换的数量进行分区

让K_i成为i身份转换出现在给定排列中的事件。 请注意，这构成了所有可能结果的详尽划分：

• 没有排列可以同时有两个不同数量的身份转换，
• 所有可能的排列必须有0到N身份转换。

因此，我们可以应用全概率法则 ：

现在我们终于可以利用这个分区了。 请注意，当非身份转置的数量是奇数时，数组无法保持不变*。 从而：

* _{从群论看，排列是偶数或奇数，但从来都不是。 因此奇数排列不能是身份排列（因为排列是偶数）。}

3）确定概率

所以我们现在必须为Ni确定两个概率：

1. 
2. 

第一学期

第一届， 表示用i身份换位获得置换的概率。 因为对于for循环的每一次迭代，这就变成了二项式：

• 结果与之前的结果无关，而且
• 创build身份转换的概率是相同的，即1/N

因此，对于N试验，获得身份转换的概率是：

第二学期

所以，如果你已经做到这一点，我们已经减less了发现的问题 对于N - i甚至。 这代表了获得身份置换的概率，因为换位是身份。 我用一种天真的计数方法来确定在可能的排列数量上达到身份排列的方法的数量。

首先考虑置换(n, m)和(m, n)等价。 然后，让M是可能的非身份排列的数量。 我们会经常使用这个数量。

这里的目标是确定一系列转置可以组合以形成身份置换的方式的数量。 我将尝试一起构造N = 4一个例子的一般解决scheme。

---

让我们考虑所有身份换位（ 即 i = N = 4 ）的i = N = 4 。 让X表示身份转换。 对于每个X ，有N可能性（它们是： n = m = 0, 1, 2, ... , N - 1 ）。 因此，实现身份置换有N^i = 4^4可能性。 为了完整性，我们加上二项式系数C(N, i) ，考虑身份换位的sorting（这里它只是等于1）。 我试图用下面的元素的物理布局和下面的可能性来描述这个：

 I = _X_ _X_ _X_ _X_ N * N * N * N * C(4, 4) => N^N * C(N, N) possibilities 

现在没有明确地replaceN = 4和i = 4 ，我们可以看一般情况。 结合以上发现的分母，我们发现：

这很直观。 实际上，除了1其他任何值都可能会让你感到震惊。 想一想：我们给出了所有N转置被认为是身份的情况。 在这种情况下arrays可能会保持不变？ 显然， 1 。

---

现在，再次对于N = 4 ，我们考虑2个身份转置（ 即， i = N - 2 = 2 ）。 作为一个惯例，我们将把两个身份放在最后（并在稍后的sorting中考虑）。 我们现在知道，我们需要挑选两个转换，这些转换在组成时将成为身份置换。 让我们把任何元素放在第一个位置，称之为t1 。 如上所述，假设t1不是一个身份（这不可能如我们已经放置的那样）有M可能性。

 I = _t1_ ___ _X_ _X_ M * ? * N * N 

唯一可能进入第二个点的元素是t1的倒数，实际上是t1 （这是逆唯一唯一的一个）。 我们再次包含二项式系数：在这种情况下，我们有4个开放的位置，我们正在寻找2个身份排列。 我们可以做多less种方式？ 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没有身份转置的情况（ 即 i = N - 4 = 0 ）。 由于有很多可能性，它开始变得棘手，我们必须小心不要重复计数。 我们首先在第一个地方放置一个元素，然后找出可能的组合。 以最简单的方式：同一个换位4次。

 I = _t1_ _t1_ _t1_ _t1_ M * 1 * 1 * 1 => M possibilities 

现在我们来考虑两个独特的元素t1和t2 。 t1有M可能性， t1只有M-1可能（因为t2不能等于t1 ）。 如果我们用尽所有的安排，我们会留下以下模式：

 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 * ? * ? * ? 

我们还不能说有多less可能，现在我们将在一分钟内看到为什么。

我们现在把t1放在第三位。 注意， t1必须去那里，因为如果要去最后一个地方，我们只是重新创build上面的(3)rd安排。 双重计数是不好的！ 这将第三个独特元素t3留给最后的位置。

 I = _t1_ _t2_ _t1_ _t3_ M * ? * 1 * ? 

那么为什么我们不得不花一点时间仔细考虑t2的数量呢？ 换位t1和t2 不能是不相交的排列（ 即，它们必须共有一个（并且只有一个，因为它们也不能相等） n或m ）。 原因是因为如果它们不相交，我们可以交换排列顺序。 这意味着我们会重复(1)st安排。

说t1 = (n, m) 。 对于某些x和y ， t2必须是(n, x)或(y, m)的forms，以便不分离。 请注意， x可能不是n或m ， y可能不是n或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 

最后，把所有这些放在一起：

---

4）把它放在一起

就是这样了。 向后倒退，把我们发现的东西代入步骤2中给出的原始总和。我计算了下面N = 4情况下的答案。 它与在另一个答案中find的经验数字非常接近！

          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 ，有很多方法可以用四个独特的元素来创build身份，这些元素在上面没有说明。 随着排列变长（就我所知，排列方式变得越来越难以计算）。

无论如何，我绝对不能在面试的范围内做这样的事情。 如果我幸运的话，我会尽可能分母的一步。 除此之外，这似乎很讨厌。

Answer 2

非常好奇，为什么这些人会问这样奇怪的概率？

问这样的问题是因为他们允许面试官深入了解受访者

• 能力阅读代码（非常简单的代码，但至less有一些东西）
• 分析algorithm以识别执行path的能力
• 应用逻辑找出可能的结果和边缘情况的技巧
• 推理和解决问题的能力
• 沟通和工作技巧 – 他们是否提出问题，或根据手头的信息单独工作

… 等等。 揭露受访者这些属性的问题的关键是要有一段看似简单的代码。 这样摆脱了非编码员卡住的冒名顶替者; 傲慢地跳到错误的结论; 懒惰的或者低于标准的计算机科学家find一个简单的解决scheme并停止寻找。 正如他们所说，通常不是你是否得到了正确的答案，而是你是否对你的思考过程留下了深刻的印象。

---

我也会试着回答这个问题。 在一次采访中，我会解释自己，而不是提供一个单行的书面答案 – 这是因为即使我的“答案”是错误的，我也能够展示逻辑思维。

A将保持不变 – 即在相同位置的元素 – 何时

• m == n在每一次迭代（所以每个元素只与自己交换）; 要么
• 任何被交换的元素都被交换回原来的位置

第一种情况是duedl0r给出的“简单”情况，数组没有改变的情况。 这可能是答案，因为

数组A保持不变的概率是多less？

如果数组在i = 1变化，然后在i = 2恢复原状态，但它不是“保持不变” – 它被改变了，然后又改回来了。 这可能是smartass的技术性。

然后考虑元素交换和交换的机会 – 我认为这个计算在面试中高于我的头。 显而易见的考虑是，这不需要是一个变化 – 换回交换，可以很容易地在三个元素之间进行交换，交换1和2，然后交换2和3,1和3，最后交换2和3。继续，可以在这样的“循环”之间交换4,5个或更多的项目。

事实上，不考虑数组不变的情况，考虑改变的情况可能会更简单。 考虑这个问题是否可以映射到帕斯卡三angular形这样的已知结构上 。

---

这是一个难题。 我同意在面试中解决这个问题太难了，但这并不意味着在面试中要求很难。 可怜的候选人没有答案，一般候选人会猜出明显的答案，好的候选人会解释为什么这个问题太难回答。

我认为这是一个“开放式”的问题，让面试官洞察候选人。 因此，即使在面试中很难解决，在面试中问一个很好的问题。 除了检查答案是对还是错外，还有更多的问题。

Answer 3

下面是C代码来计算rand可以产生的2N元组值的数目并计算概率。 从N = 0开始，它显示1,1,8,135,4480,189125和12450816的计数，概率分别为1,1，.5，.185185，.0683594，.0193664和.00571983。 计数不出现在整数序列百科全书中 ，所以无论我的程序有一个错误，或者这是一个非常模糊的问题。 如果是这样的话，这个问题并不打算由求职者解决，而是揭露他们的一些思考过程，以及他们如何处理挫折。 我不认为这是一个很好的面试问题。

 #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; } 

Answer 4

该algorithm的行为可以被build模为对称组 S _N上的马尔可夫链 。

基本

数组A的N个元素可以排列在N ！ 不同的排列。 让我们将这些排列从1到N编号，例如通过词典sorting。 因此，algorithm中任何时候arraysA的状态都可以用排列数来充分表征。

例如，对于N = 3，所有3的一个可能的编号！ = 6个排列可能是：

1. ABC
2. ACB
3. BAC
4. BCA
5. 出租车
6. CBA

状态转换概率

在algorithm的每一步中， A的状态保持不变，或者从这些排列之一转换到另一个排列。 我们现在对这些状态变化的可能性感兴趣。 让我们称Pr（ i → j ）在单次循环迭代中状态从置换i变为置换j的概率。

当我们从[0， N -1]的范围内统一地selectm和n时 ，有N 2个可能的结果，每一个结果都是相同的。

身分

对于这些结果中的N个 m = n成立，所以排列没有变化。 因此，

。

换位

其余的N 2 – N个案例是换位，即两个元素交换其位置，因此排列改变。 假设这些换位之一在位置x和y交换元素。 有两种情况可以通过algorithm产生这种换位：或者m = x ， n = y或者m = y ， n = x 。 因此，每个换位的概率是2 / N²。

这与我们的排列有什么关系？ 让我们调用两个置换i和j 邻居当且仅当存在将i变换成j的换位（反之亦然）。 我们可以得出结论：

转换matrix

我们可以将概率Pr（ i → j ）排列在转移matrixP∈[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 ）是从置换开始的概率，我们一步转换到置换k ，然后过渡到置换j 。 总结所有中间置换k因此给我们两步从i过渡到j的总概率。

这个论点可以扩展到P的更高的权力。 一个特殊的后果是以下几点：

p ^{（ N ）} _ii是在N个步骤之后返回到排列i的概率，假设我们开始于排列i 。

例

我们用N = 3来玩这个。我们已经有了一个排列的编号。 相应的转换matrix如下：

P与自身的乘法给出：

另一个乘法产生：

主对angular线的任何元素给我们所需的概率，即_15/81或_5/27 。

讨论

虽然这种方法在math上是合理的，并且可以应用于N的任何值，但这种forms并不是很实用。 转换matrixP有N ！2个条目，变得非常快。 即使N = 10，matrix的大小也已经超过了13万亿次。 这个algorithm的一个天真的实现似乎是不可行的。

但是，与其他提议相比，这种方法是非常有条理的，不需要复杂的推导，除了找出哪些排列是邻居。 我的希望是，这种结构可以被利用来find一个更简单的计算。

例如，可以利用P的任何幂的所有对angular元素都相等的事实。 假设我们可以很容易地计算P ^N的轨迹，那么解就是tr（ P ^N ）/ N ！。 P ^N的轨迹等于其特征值的N次幂之和。 所以如果我们有一个有效的algorithm来计算P的特征值，我们将被设置。 但是，我还没有进一步探讨这个比计算N = 5的特征值。

Answer 5

容易观察边界1 / n ⁿ <= p <= 1 / n。

这是一个不完全的想法，显示一个逆指数上限。

你从{1,2，…，n} 2n次绘制数字。 如果它们中的任何一个都是唯一的（只发生一次），那么数组肯定会被改变，因为元素已经消失，不能在原来的位置返回。

固定数是唯一的概率是2n * 1 / n *（1-1 / n）^（2n-1）= 2 *（1-1 / n）^（2n-1） ² ，因为你select在哪个试图得到它，1 / n你试过，（1-1 / n）^（2n-1），你没有得到它其他尝试]

如果事件是独立的，那么你就有机会得到所有数字都不是唯一的（2 / e ² ）^ n，这意味着p <= 0（（2 / e ² ）^ n）。 不幸的是，他们不是独立的。 我觉得这个界限可以用更复杂的分析来展示。 关键字是“球和篮子的问题”。

Answer 6

一个简单的解决scheme是

p> = 1 / N ^N

因为一个可能的方式数组保持不变，如果每次迭代m = n 。 而m等于n ，可能性为1 / N

这肯定比这更高。 问题是多less..

第二个想法：人们也可以争辩说，如果随机混洗一个数组，每个排列的概率是相等的。 既然有n! 排列的可能性只有一个（我们在开始）是

p = 1 / N！

这比以前的结果好一点。

正如所讨论的，该algorithm是有偏见的。 这意味着不是每个排列都有相同的概率。 所以1 / N! 不完全确切。 你必须弄清楚排列的分布是如何的。

Answer 7

仅供参考，不确定上面的限制（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) 

Answer 8

每个人都假设A[i] == i没有明确说明。 我也要做这个假设，但是请注意，概率取决于内容。 例如，如果A[i]=0 ，则所有N的概率= 1。

以下是如何做到这一点。 设P(n,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换位的数组来进行一个不是中性的换位。

编辑：-2而不是-1 P（n-1,0）

Answer 9

这不是一个完整的解决scheme，但至less是这样的。

采取一组特定的掉期没有效果。 我们知道，它的交换最终会形成一堆不同规模的循环，总共使用n交换。 （就此而言，无效的交换可以被认为是大小为1的循环）

也许我们可以

1）根据循环的大小将它们分成几组
2）计算获得每个组的方法的数量。

（主要的问题是有很多不同的团体，但是我不确定如果你不考虑不同的分组，你是怎么计算的）。

Answer 10

有趣的问题。

我想答案是1 / N，但我没有任何证据。 当我find一个certificate，我会编辑我的答案。

到目前为止，

如果m == n，则不会更改该数组。 得到m == n的概率是1 / N，因为有N ^ 2个选项，并且对于每个0 <= i <= N-1，只有N是合适的（（i，i））。

因此，我们得到N / N ^ 2 = 1 / N。

表示Pk经过k次迭代后的大小为N的数组保持不变的概率。

P1 = 1/N. (As we saw below)

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. (the first for m == n, the second for m != n)

I have to think more about what X equals. (X is just a replacement for the real formula, not a constant or anything else)

 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. 

EDIT : I want to introduce another approach:

We can classify swaps to three groups: constructive swaps, destructive swaps and harmless swaps.

Constructive swap is defined to be a swap that cause at least one element to move to its right place.

Destructive swap is defined to be a swap that cause at least one element to move from its correct position.

Harmless swap is defined to be a swap that does not belong to the other groups.

It is easy to see that this is a partition of all possible swaps. (intersection = empty set).

Now the claim I want to prove:

  The array will remain the same if and only if the number of Destructive swap == Constructive swap in the iterations. 

If someone has a counter-example, please write it down as a comment.

If this claim is correct, we can take all combinations and sum them – 0 harmless swaps, 1 harmless swaps,..,N harmless swaps.

And for each possible k harmless swap, we check if Nk is even, if no, we skip. If yes, we take (Nk)/2 for destructive, and (Nk) for constructive. And just look all possibilities.

Answer 11

I would model the problem as a multigraph where nodes are elements of the array and swaps is adding an un-directed(!) connection between them. Then look for loops somehow (all nodes is a part of a loop => original)

Really need to get back to work! 🙁

Answer 12

well, from mathematical perspective:

to have the array elements swapped at the same place every time, then the Rand(N) function must generate the same number twice for int m, and int n. so the probability that the Rand(N) function generates the same number twice is 1/N. and we have Rand(N) called N times inside the for loop, so we have probability of 1/(N^2)

Answer 13

Naive implementation in C#. The idea is to create all the possible permutations of initial array and enumerate them. Then we build a matrix of possible changes of state. Multiplying matrix by itself N times we will get the matrix showing how many ways exists that lead from permutation #i to permutation #j in N steps. Elemet [0,0] will show how many ways will lead to the same initial state. Sum of elements of row #0 will show total number of different ways. By dividing former to latter we get the probability.

In fact total number of permutations is 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; } } } 

Answer 14

The probability that m==n on each iteration, then do that N times. P(m==n) = 1/N. So I think P=1/(n^2) for that case. But then you have to consider the values getting swapped back. So I think the answer is (text editor got me) 1/N^N.

Answer 15

Question: what is the probability that array A remains the same? Condition: Assume that the array contains unique elements.

Tried the solution in Java.

Random swapping happens on primitive int array. In java method parameters are always passed by value so what happens in swap method does not matter as a[m] and a[n] elements of the array (from below code swap(a[m], a[n]) ) are passed not complete array.

The answer is array will remain same. Despite of condition mentioned above. See below java code sample:

 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(); } } 

示例输出：

Filling array: Printing array: 3 1 1 4 9 7 9 5 9 5 Swapping array: Printing array: 3 1 1 4 9 7 9 5 9 5