阵列保持不变的概率是多少？-Java 学习之路

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

给定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]);
}

EDIT: 请注意，种子不固定 .

阵列A保持不变的概率是多少？
假设数组包含唯一元素 .

15 回答

4
好吧，我对这个有一点乐趣 . 我第一次看到问题时首先想到的是群论（特别是对称群Sn） . for循环通过在每次迭代中组合转置（即交换）简单地在Sn中构建置换σ . 我的数学并不是那么壮观，而且我有点生疏，所以如果我的符号与我无关 .

概述

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

我的解决方案尝试遵循以下过程：
- 考虑所有可能的排列（即我们的数组的重新排序）
- 根据它们包含的所谓身份转置的数量，将这些排列分成不相交的集合 . 这有助于将问题简化为甚至排列 .
- 确定在置换是偶数（和特定长度）的情况下获得身份置换的概率 .
- 求和这些概率以获得阵列不变的总体概率 .
1）可能的结果

请注意，for循环的每次迭代都会创建一个交换（或转置），从而产生两种情况之一（但从不两者）：
- 交换了两个元素 .
- 元素与自身交换 . 对于我们的意图和目的，数组不变 .
我们标记了第二个案例 . 让我们定义一个身份转置如下：

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

对于列出的代码的任何给定运行，我们组成 N 转置 . 此"chain"中可能出现 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 身份转置之间 .
因此我们可以应用Law of Total Probability：
现在我们终于可以利用分区了 . 请注意，当非同一性转置的数量为奇数时，阵列无法保持不变* . 从而：
*从群论来看，排列是偶数或奇数，但从不两者兼而有之 . 因此，奇数置换不能是身份置换（因为身份置换是偶数） .

3）确定概率

所以我们现在必须确定 N-i 的两个概率：
第一学期

第一项

表示通过 i 身份转置获得排列的概率 . 这对于for循环的每次迭代都是二项式：
- 结果与之前的结果无关，并且
- 创建身份转置的概率是相同的，即 1/N .
因此，对于 N 试验，获得 i 身份转换的概率是：
第二学期

所以，如果你已经做到这一点，我们已经将问题减少到 N - i 为 N - i 甚至 . 这代表了获得身份置换的概率，因为转置是身份的.1383938 . 我使用一种天真的计数方法来确定在可能的排列数量上实现身份置换的方式的数量 .

首先考虑相当的排列 (n, m) 和 (m, n) . 然后，让 M 为可能的非身份排列的数量 . 我们会经常使用这个数量 .
这里的目标是确定可以组合转置集合以形成身份置换的方式的数量 . 我将尝试与 N = 4 的示例一起构建一般解决方案 .

让我们考虑具有所有身份转置的 N = 4 案例（即 i = N = 4 ） . 设 X 表示身份转置 . 对于每个 X ，有 N 可能性（它们是： n = m = 0, 1, 2, ... , N - 1 ） . 因此，存在实现身份置换的可能性 . 为了完整性，我们添加二项式系数 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 . t1 的可能性为 t1 ， 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   *  ?   *  ?  *  ?
```
我们还不能说有多少可能存在，我们将在一分钟内看到原因 .

我们现在将_1383988放在第三位 . 注意， t1 必须去那里，因为如果要进入最后一个位置，我们只是重新创建上面的 (3)rd 排列 . 重复计算很糟糕！这将第三个唯一元素 t3 留在最终位置 .
```
I  =  _t1_   _t2_   _t1_   _t3_ 
       M   *  ?   *  1  *   ?
```
那么为什么我们要花一点时间更仔细地考虑 t2 的数量呢？转置 t1 和 t2 cannot 是不相交的排列（即它们必须共享一个（并且只有一个，因为它们也不能相等）它们的 n 或 m ） . 这样做的原因是因为如果它们是不相交的，我们可以交换排列的顺序 . 这意味着我们将重复 (1)st 安排 .

说 t1 = (n, m) . 对于某些 x 和 y ， t2 的形式必须为 (n, x) 或 (y, m) 才能不相交 . 请注意 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) . 注意这是 not 与 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 换位，有明确的方法来创建具有四个独特元素的身份，这些元素在上面没有说明 . 随着排列变得越来越长（从我可以看出......），方式的数量似乎变得越来越难以计算 .

无论如何，我绝对不能在面试范围内做这样的事情 . 如果我幸运的话，我会达到分母步骤 . 除此之外，它似乎非常讨厌 .
回复于 2024-04-20T11:40:04+08:00
1
非常好奇地知道为什么这些人会对概率提出如此奇怪的问题？

这样的问题被问到，因为它们允许面试官深入了解受访者
- 能力读取代码（非常简单的代码，但至少有些东西）
- 分析算法以识别执行路径的能力
- 应用逻辑来发现可能的结果和边缘情况的技能
- 推理和解决问题的技巧，因为他们解决了这个问题
- 沟通和工作技能 - 他们提出问题，或根据手头的信息孤立地工作
... 等等 . 有一个问题暴露受访者的这些属性的关键是要有一段看似简单的代码 . 这会破坏非编码器卡住的冒名顶替者;傲慢的跳到了错误的结论;懒惰或低于标准的计算机科学家找到一个简单的解决方案并停止寻找 . 通常，正如他们所说，不是你得到了正确的答案，而是你是否对你的思维过程留下了深刻的印象 .

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

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

每次迭代都
- m == n （这样每个元素只与自身交换）;要么
- 交换的任何元素都被交换回原始位置
第一种情况是duedl0r给出的“简单”情况，即数组未被更改的情况 . 这可能是答案，因为

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

如果数组在 i = 1 处更改，然后在 i = 2 处返回，则's in the original state but it didn' t 'remain the same' - 已更改，然后更改回来 . 这可能是一个聪明的技术性 .

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

实际上，不考虑数组未更改的情况，考虑更改数据的情况可能更简单 . 考虑是否可以将此问题映射到像Pascal's triangle这样的已知结构 .

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

我认为这是一个问题，让面试官能够洞察候选人 . 出于这个原因，尽管在面试过程中难以解决，但在面试中提问是个好问题 . 除了检查答案是对还是错之外，还有更多的问题 .
回复于 2024-04-20T11:40:04+08:00

下面是C代码计算rand可以产生的2N元组索引的值的数量并计算概率 . 从N = 0开始，它显示计数1,1,8,135,4480,189125和12450816，概率为1,1，.5，.185185，.0683594，.0193664和.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;
}

回复于 2024-04-20T11:40:04+08:00

1
算法的行为可以在symmetric group SN上建模为Markov chain .

基础知识

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

例如，对于N = 3，所有3个中的一个可能编号！ = 6个排列可能是：
- a b c
- a c b
- b a c
- b c a
- c a b
- c b
州转移概率

在算法的每个步骤中， 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 / N 2 .

这与我们的排列有什么关系？当且仅当存在将i转换为j的转置时（反之亦然），让我们将两个置换称为i和j neighbors . 然后我们可以得出结论：

过渡矩阵

我们可以将概率Pr（i→j）排列在转移矩阵 P ∈[0,1] N！×N！中 . 我们定义

pij = Pr（i→j），

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

Pr（i→j）= Pr（j→i），

这意味着 P 是对称的 .

现在的关键点是观察当我们自己乘以 P 时会发生什么 . 取 P ²的任何元素p（2）ij：

乘积Pr（i→k）·Pr（k→j）是在置换中开始的概率，我们在一个步骤中转换到置换k，并且在另一个后续步骤之后转换到置换j . 因此，对所有中间排列k求和，得出 transitioning from i to j in 2 steps 的总概率 .

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

p（N）ii是在N个步骤之后返回到置换i的概率，假设我们从置换i开始 .

示例

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

将 P 与其自身相乘得出：

另一个乘法产量：

主对角线的任何元素给出了我们想要的概率，即15/81或5/27 .

讨论

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

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

例如，人们可以利用 P 的任何幂的所有对角元素都相等的事实 . 假设我们可以很容易地计算出 P N的轨迹，那么解决方案就是这么简单tr（ P N）/ N！ . P N的轨迹等于其特征值的N次幂之和 . 因此，如果我们有一个有效的算法来计算 P 的特征值，我们将被设置 . 然而，我没有比计算N = 5的特征值进一步探索这一点 .
回复于 2024-04-20T11:40:04+08:00
21

很容易观察到1 / nn <= p <= 1 / n的界限 .

这是显示反指数上限的不完整概念 .

你从{1,2，..，n}中抽取数字2n次 . 如果它们中的任何一个是唯一的（恰好发生一次），那么数组肯定会被更改，因为元素已经消失并且无法返回其原始位置 .

固定数是唯一的概率是2n * 1 / n *（1-1 / n）^（2n-1）= 2 *（1-1 / n）^（2n-1），这是同样的2 / e2离开了0. [2n因为你选择了哪个尝试得到它，1 / n你得到它的尝试，（1-1 / n）^（2n-1）你没有得到它在其他尝试]

如果事件是独立的，那么你将得到所有数字都不唯一的机会是（2 / e2）^ n，这意味着p <= O（（2 / e2）^ n） . 不幸的是，他们不是独立的 . 我觉得可以通过更复杂的分析来展示界限 . 关键字是"balls and bins problem" .

回复于 2024-04-20T11:40:04+08:00
1

一个简单的解决方案是

p> = 1 / NN

由于数组保持不变的一种可能方式是每次迭代都是 m = n . m 等于 n ，可能 1 / N .

它肯定比那更高 . 问题是多少..

第二个想法：人们也可以争辩说，如果你随机地改变一个数组，每个排列都有相同的概率 . 由于存在 n! 排列，因此只获得一个（我们在开头的那个）的概率是

p = 1 / N！

这比以前的结果好一点 .

如上所述，算法是有偏见的 . 这意味着并非每个排列具有相同的概率 . 所以 1 / N! 并不完全准确 . 你必须弄清楚排列的分布情况 .

回复于 2024-04-20T11:40:04+08:00

仅供参考，不确定上述（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)

回复于 2024-04-20T11:40:04+08:00

10
每个人都认为 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）
回复于 2024-04-20T11:40:04+08:00
3

这不是一个完整的解决方案，但它至少是一些东西 .

采取一组没有效果的特定交换 . 我们知道，它的交换最终会形成一堆不同大小的循环，使用总共 n 掉期 . （出于此目的，无效的交换可被视为大小为1的循环）

也许我们可以

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

（主要问题是有很多不同的群体，但如果你不考虑不同的群体，我实际上会计算出来 . ）

回复于 2024-04-20T11:40:04+08:00
0
有趣的问题 .

我认为答案是1 / N，但我没有任何证据 . 当我找到证据时，我会编辑我的答案 .

到目前为止我得到了什么：

如果m == n，则不会更改数组 . 得到m == n的概率是1 / N，因为有N ^ 2个选项，并且只有N是合适的（（i，i）每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.
```
EDIT : 我想介绍另一种方法：

我们可以将掉期分为三类：建设性掉期，破坏性掉期和无害掉期 .

构造性交换被定义为交换，导致至少一个元素移动到它正确的地点 .

破坏性交换被定义为交换，导致至少一个元素从其正确位置移动 .

无害交换被定义为不属于其他组的交换 .

很容易看出这是所有可能的交换的分区 . （intersection = empty set） .

现在我要证明的主张：
```
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）表示建设性 . 只看所有可能性 .
回复于 2024-04-20T11:40:04+08:00
3

我将问题建模为一个多图，其中节点是数组的元素，交换是在它们之间添加一个非定向（！）连接 . 然后以某种方式寻找循环（所有节点都是循环的一部分=>原始）

真的需要重新开始工作！ :(

回复于 2024-04-20T11:40:04+08:00
1

好吧，从数学的角度来看：

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

回复于 2024-04-20T11:40:04+08:00

在C＃中实现天真 . 我们的想法是创建初始数组的所有可能的排列并枚举它们 . 然后我们 Build 一个可能的状态变化矩阵 . 将矩阵乘以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;
        }
    }
}

回复于 2024-04-20T11:40:04+08:00

9

每次迭代时m == n的概率，然后进行N次 . P（m == n）= 1 / N.所以我认为对于那种情况P = 1 /（n ^ 2） . 但是你必须考虑换回的值 . 所以我认为答案是（文本编辑得到我）1 / N ^ N.

回复于 2024-04-20T11:40:04+08:00

问题：阵列A保持不变的概率是多少？条件：假设数组包含唯一元素 .

尝试用Java解决方案 .

随机交换发生在原始int数组上 . 在java方法中，参数总是按值传递，所以在swap方法中发生的事情并不重要，因为数组的[m]和[n]元素（来自下面的代码交换（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

回复于 2024-04-20T11:40:04+08:00

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

15 回答

概述

1）可能的结果

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

3）确定概率

第一学期

第二学期

4）全部放在一起

正确

基础知识

州转移概率

身份

换位

过渡矩阵

示例

讨论

相关问题