一个简单的解决方案是

P > = 1/N^N

因为数组保持不变的一种可能方式是每次迭代都使用 m = n。m等于 n可能是 1 / N。

肯定比那个高，问题是有多高。

第二个想法: 人们也可以说，如果你随机洗牌一个数组，每个排列都有相同的概率。因为存在 n!排列，所以只得到一个排列的概率(我们在开始时得到的那个排列)是

P = 1/N！

比之前的结果好一点。

正如所讨论的，该算法是有偏的。这意味着不是每种排列都有相同的概率。所以 1 / N!不是很精确。你必须找出排列的分布情况。

每次迭代 m = = n 的概率，然后做 N 次。P (m = = n) = 1/N.我认为 P = 1/(n ^ 2)。但是你必须考虑这些值被交换回来。所以我认为答案是(文本编辑器得到的)1/N ^ 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 将保持不变-即元素在相同的位置-当

• 在每次迭代中使用 m == n(以便每个元素只与自身交换) ; 或者
• 任何被交换的元素都会被交换回原来的位置

第一种情况是 duedl0r 给出的“ simple”情况，即数组没有更改的情况。这可能就是答案，因为

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

如果数组在 i = 1处发生变化，然后在 i = 2处恢复，那么它就处于原始状态，但是它并没有“保持不变”——它被改变了，然后又被改变回来。这可能是个自作聪明的技术问题。

然后考虑到元素被交换和交换回来的可能性——我认为在一次采访中这种计算超出了我的能力范围。显而易见的考虑是，这不需要一个变更-变更回交换，可以很容易地在三个元素之间进行交换，交换1和2，然后2和3,1和3，最后2和3。而且，可能有4,5或更多像这样的“循环”项目之间的互换。

实际上，与其考虑数组没有变化的情况，不如考虑 是变化的情况。考虑是否可以将这个问题映射到像 帕斯卡三角形这样的已知结构。

这是个难题。我同意在面试中解决这个问题太难了，但这并不意味着在面试中问这个问题太难了。差的候选人不会有答案，一般的候选人会猜出显而易见的答案，而好的候选人会解释为什么这个问题太难回答。

我认为这是一个“开放式”的问题，可以让面试官了解应聘者。因此，尽管在面试中这个问题很难解决，但在面试中却是一个 很好的问题。问一个问题不仅仅是检查答案是对是错。

虽然不能完全解决问题，但至少是个办法。

选择一组没有效果的特定互换。我们知道，肯定是这种情况，它的掉期最终形成了一大堆不同大小的循环，使用总的 n掉期。(为此，没有效果的交换可以被认为是大小为1的循环)

也许我们可以

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

(主要的问题是有一个不同组的 吨，但我不确定如果不考虑不同的组，你实际上会如何计算这个。)

下面是 C 代码，用于计算兰德可以产生并计算概率的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;
}

很容易观察到边界1/n^N < = p < = 1/n。

这里是一个不完整的想法，显示一个反指数上界。

您正在从{1,2，。.2n 次。如果它们中的任何一个是唯一的(只出现一次) ，数组肯定会被更改，因为元素已经消失，不能返回到原来的位置。

一个固定数是唯一的概率是2n * 1/n * (1-1/n) ^ (2n-1) = 2 * (1-1/n) ^ (2n-1) ，这是不对称的2/e²，有界远离0。[2n，因为你选择了你得到它的方法，1/n，你在那次尝试中得到了它，(1-1/n) ^ (2n-1) ，你在其他尝试中没有得到它]

如果事件是独立的，那么所有的数字都是非唯一的就是(2/e²) ^ n，这意味着 p < = O ((2/e²) ^ n)。不幸的是，他们并不是独立的。我觉得这个界限可以用更复杂的分析来表示。关键词是“球和箱子问题”。

_{这次我玩得很开心。当我第一次阅读这个问题时，我想到的第一件事是群论(特别是对称群 SN)。For 循环通过在每次迭代中组合换位(即交换)在 SN中简单地构建一个置换 σ。我的数学并不是那么惊人，而且我有点生疏了，所以如果我的符号有问题的话。}

概述

设置 A为数组在排列之后不变的事件。我们最终被要求找到事件 A，Pr(A)的概率。

我的解决方案试图遵循以下程序:

1. 考虑所有可能的排列(即数组的重新排序)
2. 根据这些排列所包含的所谓 身份转换的数量，将它们划分为 分离集。这有助于将问题减少到仅 甚至排列。
3. 给定排列是偶数(和特定长度) ，确定获得恒等排列的概率。
4. 将这些概率相加，得到数组不变的总概率。

1)可能的结果

请注意，for 循环的每次迭代都会创建一个交换(或 换位) ，它会产生以下两种结果之一(但绝不会同时产生两种结果) :

1. 交换了两个元素。
2. 一个元素与它自己交换。对于我们的意图和目的，数组是不变的。

我们给第二种情况贴上标签。让我们定义一个 身份转换身份转换如下:

当一个数字与它自己交换时，就会出现 身份转换身份转换。 也就是说，当 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) ，并且数组被更改。

2)基于身份转换次数的划分

设 K_i为 i同一性转换在给定排列中出现的事件。请注意，这是对所有可能结果的详尽划分:

• 任何排列都不能同时有两个不同数量的同一性转换，并且
• 所有可能的排列必须在 0和 N同一性转换之间。

因此，我们可以应用 全概率公式:

现在我们终于可以利用这个分区了。注意，当 没有身份转换的数量为奇数时，数组不可能保持不变 * 。因此:

* _{从群论的角度来看，排列是偶数或奇数，但不可能两者都是。因此奇数排列不能是单位置换(因为单位置换是偶数)。}

3)确定概率

因此，我们现在必须确定 N-i的两种概率:

第一学期

第一个术语 < img src = “ https://i.stack.imgur.com/z2aNn.png”alt = “ Pr (K _ i)”> 表示获得具有 i身份转换的排列的概率。这是二项式的，因为 for 循环的每次迭代:

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

因此，对于 N试验，获得 i身份转换的可能性是:

第二任期

因此，如果您已经做到了这一点，我们甚至可以将问题简化为找到 N - i的 < img src = “ https://i.stack.imgur.com/YAoOl.png”alt = “ Pr (A | K _ i)”> 。这表示给定转位的 i是恒等式时获得恒等式排列的概率。我使用一种简单的计数方法来确定实现身份置换的方法的数量超过可能的置换的数量。

首先考虑排列 (n, m)和 (m, n)等价。然后，让 M成为可能的非恒等排列数。我们将经常使用这个数量。

这里的目标是确定组合转换集合以形成身份置换的方式的数量。我将尝试与 N = 4示例一起构建通用解决方案。

让我们考虑具有所有身份转换的 N = 4情况(也就是说。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 = 4和 i = 4，我们可以看一下一般情况。结合以上所发现的分母，我们发现:

这是直觉。事实上，除了 1之外的任何其他值都可能会提醒您。想想看: 我们被给定的情况下，所有的 N转换被说成是恒等式。在这种情况下，数组没有改变的可能性是多少？显然是 1。

现在，再次对于 N = 4，让我们考虑2个身份转换(也就是说。i = N - 2 = 2)。作为一种约定，我们将把两个标识放在最后(并说明以后的排序)。我们现在知道，我们需要选择两个转换，当组成，将成为身份置换。让我们在第一个位置放置任何元素，称之为 t1。如上所述，有 M的可能性假设 t1不是一个身份(它不能是因为我们已经放置了两个)。

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

剩下的唯一可能进入第二个点的元素是 t1的逆元素，实际上是 t1(这是唯一的逆元素)。我们再次包括二项式系数: 在这种情况下，我们有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的可能性，而 t2只有 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   *  ?   *  ?  *  ?

我们还不能说有多少可能的 t2s 还没有，我们将看到为什么在一分钟。

我们现在把 t1放在第三位。注意，t1必须去那里，因为如果我们去最后一个地方，我们将只是重新创建 (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)的形式，以便不不相交。请注意，x可能不是 n或 m和 y许多不是 n或 m。因此，t2可能的排列数实际上是 t23。

回到我们的布局:

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案例的答案。它与在另一个答案中发现的经验数字非常接近！

N  =  4
M  =  6   _________ _____________ _________
| Pr(K_i) | Pr(A | K_i) | Product |
_________|_________|_____________|_________|
|         |         |             |         |
|  i = 0  |  0.316  |  120 / 1296 |  0.029  |
|_________|_________|_____________|_________|
|         |         |             |         |
|  i = 2  |  0.211  |    6 / 36   |  0.035  |
|_________|_________|_____________|_________|
|         |         |             |         |
|  i = 4  |  0.004  |    1 / 1    |  0.004  |
|_________|_________|_____________|_________|
|             |         |
|     Sum:    |  0.068  |
|_____________|_________|

正确

如果群论在这里有一个应用的结果，那就太酷了——也许真的有！它肯定有助于完全消除所有这些乏味的计数(并将问题缩短到更优雅的程度)。我不在 N = 4工作了。对于 N > 5，给出的只是一个近似值(我不确定有多好)。如果您仔细想想，就会非常清楚为什么会这样: 例如，给定 N = 8换位，有明显的方法可以用上面没有考虑到的 四独特元素来创建身份。随着排列变得越来越长(据我所知...) ，方法的数量似乎越来越难以计算。

无论如何，我绝对不能在面试的范围内做这样的事情。如果幸运的话，我能走到分母那一步。除此之外，看起来还挺恶心的。

问: 数组 A 保持不变的概率是多少？ 条件: 假设数组包含唯一的元素。

在 Java 中尝试了该解决方案。

基元 int 数组上发生随机交换。在 java 方法中，参数总是通过值传递，所以在交换方法中发生的事情并不重要，因为数组的[ m ]和[ n ]元素(从下面的代码交换([ 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();
}
}

输出样本:

填充数组: 打印数组: 3114979595 交换数组: 打印数组: 3114979595

有趣的问题。

我认为答案是1/N，但我没有任何证据。当我找到证据时，我会修改我的答案。

直到现在:

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

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

表示在交换的 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 无害交换，我们检查 N-k 是否为偶数，如果不是，我们跳过。如果是，我们把(N-k)/2表示为破坏性的，把(N-k)表示为建设性的。看看所有的可能性。

我将把这个问题建模为一个多图，其中节点是数组的元素，交换器添加了一个无向(!)他们之间的联系。然后寻找循环(所有节点都是循环 = > 原始循环的一部分)

真该回去工作了

每个人都假设 A[i] == i，这是不明确的 我也会做这个假设，但是请注意 取决于内容。例如，如果 A[i]=0，那么对于 都是 N。

这里是如何做到这一点。让 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个坏换位的数组，并且做一个非中性的换位。

编辑: 在 P (n-1,0)中用 -2代替 -1

从数学的角度来看:

要让数组元素每次都在同一个地方交换，那么 Rand (N)函数必须为 int m 和 int n 生成相同的数字两次，所以 Rand (N)函数生成相同数字两次的概率是1/N。 我们在 for 循环中有 Rand (N)调用 N 次，所以我们有1/(N ^ 2)的概率

该算法的行为可以在 对称群 S < sub > N 上建模为 马尔可夫链。

基本知识

阵列 A的 N元素可以排列在 N中！不同的排列。让我们把这些排列从1数到 N！例如，通过词典的排序。所以算法中数组 A在任何时候的状态都可以完全拥有属性排列数。

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

1. 是 b c
2. 一个 CB
3. B a c
4. 是的
5. C a b
6. C B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B

状态转换概率

在算法的每个步骤中，A的状态要么保持不变，要么从这些排列中的一个转换到另一个。我们现在感兴趣的是这些状态变化的可能性。让我们称 Pr (< em > i → < em > j )为状态在一个循环迭代中从排列 我变为排列 J的概率。

当我们从范围[0，N-1]中均匀和独立地选择 我和 N时，有 N2可能的结果，每个结果都是同样可能的。

身份

对于这些结果的 N，我 = N保持不变，因此排列没有变化,

.

换位

其余的 N2-N病例为转位，即两个元素交换位置，因此排列发生变化。假设其中一个转换交换位置为 X和 嘿的元素。有两种情况下，这种转换可以产生的算法: 无论是 M = x，N = y或 M = y，N = x。因此，每个转位的概率是2/N2。

这和我们的排列有什么关系？让我们调用两个排列 我和 J 邻居当且仅当有一个转换，将 我转换为 J(反之亦然)。然后我们可以得出结论:

转移矩阵

我们可以在转移矩阵 P∈[0,1] ^{< em > N ! × < em > N ！}中排列概率 Pr (我→ J)

P_(法语) = Pr (我→ J) ,

其中 P < sub > ij 是 P的第1行和第2列中的条目。注意到了吗

Pr (我→ J) = Pr (J→ 我) ,

也就是说 P是对称的。

现在的关键点是观察当我们将 P乘以它本身时会发生什么。取 P2的任意元素 P⁽²⁾_[俄语]:

产物 Pr (我→ K) · Pr (K→ J)是从排列 我开始一步过渡到排列 K，再经过另一步过渡到排列 J的概率。因此，将所有中间排列 K相加，给出了在两个步骤中从 我到 J的 转换的总概率。