阵列保持不变的概率是多少？

Question

在微软的采访中已经提出了这个问题.非常好奇地知道为什么这些人会对概率提出如此奇怪的问题？

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

Answer 1

_{好吧,我对这个有一点乐趣.我第一次读到问题时首先想到的是群论(特别是对称群S n).for循环通过在每次迭代中组合转置(即交换)来简单地在S n中建立置换σ .我的数学并不是那么壮观,而且我有点生疏,所以如果我的符号与我无关.}

概观

让A我们的数组在排列后保持不变.我们最终被要求找到事件的概率A,Pr(A).

我的解决方案尝试遵循以下过程:

1. 考虑所有可能的排列(即我们的数组的重新排序)
2. 根据它们包含的所谓身份转置的数量,将这些排列分成不相交的集合.这有助于将问题简化为甚至排列.
3. 确定在置换是偶数(和特定长度)的情况下获得身份置换的概率.
4. 求和这些概率以获得阵列不变的总概率.

1)可能的结果

请注意,for循环的每次迭代都会创建一个交换(或转置),从而产生两种情况之一(但从不两者):

1. 交换了两个元素.
2. 元素与自身交换.对于我们的意图和目的,数组不变.

我们标记了第二个案例.让我们定义一个身份转置如下:

一个身份换位当一个号码与自己交换发生.也就是说,当在上面的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)确定概率

所以我们现在必须确定N-i偶数的两个概率:

1. 
2. 

第一学期

第一学期, ,表示获得具有i身份转置的排列的概率.这对于for循环的每次迭代都是二项式:

• 结果与之前的结果无关,并且
• 创建身份转置的概率是相同的,即1/N.

因此,对于N试验,获得i身份转换的概率是:

第二学期

所以,如果你已经做到这一点,我们已经把问题减少到找到了 为了N - 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个身份排列.我们有多少种方法可以做到这一点？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.有M可能t1而且只有M-1可能t2(因为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   *  ?   *  ?  *  ?  

我们还不能说t2有多少可能存在,我们将在一分钟内看到原因.

我们现在排t1在第三位.请注意,t1必须去那里,因为如果要进入最后一个位置,我们只是重新创建(3)rd上面的安排.重复计算很糟糕!这将第三个独特元素留给t3最终位置.

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

那么为什么我们要花一点时间t2更仔细地考虑一下s 的数量呢？转置t1并且t2 不能是不相交的排列(即它们必须共享一个(并且只有一个,因为它们也不能相等)它们的n或m).这样做的原因是因为如果它们是不相交的,我们可以交换排列的顺序.这意味着我们将重复计算(1)st安排.

说t1 = (n, m).t2必须是以下形式的(n, x)或(y, m)为一些x与y以是非不相交的.请注意,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下面案例的答案.它非常接近地匹配另一个答案中找到的经验数字!

         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换位,有明确的方法来创建具有四个独特元素的身份,这些元素在上面没有说明.随着排列变得越来越长(从我可以看出......),方式的数量似乎变得越来越难以计算.

无论如何,我绝对不能在面试范围内做这样的事情.如果我幸运的话,我会达到分母步骤.除此之外,它似乎非常讨厌.

Answer 2

非常好奇地知道为什么这些人会对概率提出如此奇怪的问题？

这样的问题被问到,因为它们允许面试官深入了解受访者

• 能力阅读代码(非常简单的代码,但至少有些东西)
• 能够分析算法以识别执行路径
• 应用逻辑来发现可能的结果和边缘情况的技巧
• 他们解决问题时的推理和解决问题的能力
• 沟通和工作技巧 - 他们提出问题,或根据手头的信息孤立地工作

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

我也会尝试回答这个问题.在一次采访中,我会解释自己,而不是提供一个单行的书面答案 - 这是因为即使我的"答案"是错误的,我也能够表现出逻辑思维.

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

• m == n在每次迭代中(以便每个元素只与自身交换); 要么
• 交换的任何元素都被交换回原始位置

第一种情况是duedl0r给出的"简单"情况,即数组未被更改的情况.这可能是答案,因为

阵列A保持不变的概率是多少？

如果数组发生变化i = 1然后恢复i = 2,则它处于原始状态,但它不会"保持不变" - 它被更改,然后再更改回来.这可能是一个聪明的技术性.

然后考虑元素交换和交换的可能性 - 我认为在面试中计算是在我头上.显而易见的考虑是,这不需要是一个改变 - 改变回交换,可以很容易地在三个元素之间交换,交换1和2,然后是2和3,1和3,最后是2和3.继续,可能会有4个,5个或更多像这样"循环"的项目之间的掉期交易.

事实上,而不是考虑的情况下,该阵列是不变的,它可能是简单考虑它的情况下被改变.考虑是否可以将此问题映射到Pascal三角形等已知结构上.

这是一个难题.我同意在面试中难以解决,但这并不意味着在面试中要求太难.可怜的候选人将无法得到答案,平均候选人会猜出明显的答案,而优秀的候选人将解释为什么问题难以回答.

我认为这是一个"开放式"问题,让面试官能够洞察候选人.出于这个原因,尽管在面试过程中难以解决,但在面试中提问是个好问题.除了检查答案是对还是错之外,还有更多的问题.

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

该算法的行为可以被建模为一个Markov链在对称群 小号_Ñ.

基本

数组的N个元素A可以排列成N!不同的排列.让我们将这些排列从1到N!编号,例如通过词典排序.因此,A算法中任何时候阵列的状态都可以通过置换数来完全表征.

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

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

国家转移概率

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

当我们从[0,N -1] 范围内均匀且独立地选择m和n时,存在N 2个可能的结果,每个结果都是相同的.

身分

对于这些结果中的N个,m = n成立,因此置换没有变化.因此,

.

换位

剩下的N 2 -N个案例是换位,即两个元素交换它们的位置,因此置换发生变化.假设这些转置中的一个在位置x和y处交换元素.有两种情况如何通过算法生成这种转置:m = x,n = y或m = y,n = x.因此,对于每个换位的概率为2/Ñ ².

这与我们的排列有什么关系？当且仅当存在将i转换为j的转置时(反之亦然),让我们将i和j个 邻居称为两个排列.然后我们可以得出结论:

过渡矩阵

我们可以安排的概率PR(我 → Ĵ在过渡矩阵)P ∈[0,1] ^{Ñ!× Ñ!}.我们定义

p _ij = Pr(i → j),

其中p _ij是P的第i行和第j列的条目.注意

Pr(i → j)= Pr(j → i),

这意味着P是对称的.

现在的关键点是观察当我们将P乘以时会发生什么.采取任何元素p ⁽²⁾_IJ的P ²:

产品PR(我 → ķ)·PR(ķ → Ĵ)是起始于置换的概率我我们过渡到置换ķ在一个步骤中,和过渡到置换Ĵ陆续后续步骤.求和所有在其间排列ķ因此使我们的总概率从过渡我到Ĵ在2个步骤.

这个论点可以扩展到P的更高权力.特殊后果如下:

p ^(N)_ii是在N个步骤之后返回到置换i的概率,假设我们从置换i开始.

例

让我们通过N = 3 来解决这个问题.我们已经有了排列的编号.相应的转换矩阵如下:

将P与自身相乘得出:

另一个乘法产量:

主对角线中的任何元素给我们想要的概率,这是¹⁵/₈₁或⁵/₂₇.

讨论

虽然这种方法在数学上是合理的并且可以应用于N的任何值,但是在这种形式中它不是很实用.转换矩阵P具有N!2个条目,它变得非常快.即使N = 10,矩阵的大小已超过13万亿条目.因此,该算法的简单实现似乎是不可行的.

然而,与其他提议相比,这种方法非常有条理,除了确定哪些排列是邻居之外,不需要复杂的推导.我希望这种结构化可以被利用来找到更简单的计算.

例如,人们可以利用P的任何幂的所有对角元素都相等的事实.假设我们可以很容易地计算出P ^N的轨迹,那么解就是tr(P ^N)/ N!P ^N的轨迹等于其特征值的N次幂之和.因此,如果我们有一个有效的算法来计算P的特征值,我们就会设置.然而,我没有比计算N = 5 的特征值进一步探索这一点.