この質問は、マイクロソフトのインタビューで尋ねられました。なぜこれらの人々が確率についてそれほど奇妙な質問をするのか知りたいのですが？
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ループは、反復ごとに転置（つまりスワップ）を構成することにより、Snに順列σを構築するだけです。私の数学はそれほど壮観ではなく、私は少しさびているので、私の表記が外れている場合は私に耐えられません。
順列Aの後で配列が変更されないというイベントであるとします。最終的に、イベントの確率を見つけるように求められAますPr(A)。
私のソリューションは、次の手順に従おうとします。
forループを繰り返すたびに、スワップ（または転置）が作成され、次の2つのいずれか（両方ではない）が発生することに注意してください。
2番目のケースにラベルを付けます。次のようにアイデンティティの転置を定義しましょう。
IDの転置は、番号がそれ自体と交換されるときに発生します。つまり、上記の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）があり、配列が変更されていることに注意してください。
アイデンティティの転置が特定の順列に現れるK_iイベントであるとします。iこれは、考えられるすべての結果の完全なパーティションを形成することに注意してください。
0可能なすべての順列は、Nアイデンティティの転置の間である必要があります。したがって、全確率の法則を適用できます。
これで、最終的にパーティションを利用できるようになりました。非同一性転置の数が奇数の場合、配列を変更しない方法はないことに注意してください*。したがって：
*群論から、順列は偶数または奇数ですが、両方になることはありません。したがって、奇数の順列を単位元の順列にすることはできません（単位元の順列は偶数であるため）。
したがって、次の2つの確率を決定する必要がN-iあります。
最初の項、は、同一性の転置を伴う順列を取得する確率を表しiます。forループの反復ごとに、これは二項分布であることがわかります。
1/Nです。したがって、N試験の場合、iアイデンティティの転置を取得する確率は次のとおりです。
したがって、これまでに達成した場合は、問題を均等に見つけることに減らしましたN - i。iこれは、転置が単位元である場合に、単位順列を取得する確率を表します。私は素朴なカウントアプローチを使用して、可能な順列の数に対して単位元の順列を達成する方法の数を決定します。
まず、順列(n, m)と(m, n)同等のものを検討します。次に、M可能な非同一性順列の数とします。この量を頻繁に使用します。
ここでの目標は、転置のコレクションを組み合わせて単位元列を形成する方法の数を決定することです。の例と一緒に一般的なソリューションを構築しようとしN = 4ます。
N = 4すべてのID転置（つまり ）の場合を考えてみましょう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。
さて、ここでも、 2つのアイデンティティの転置（すなわちN = 4）を考えてみましょう。慣例として、2つのIDを最後に配置します（後で注文することを考慮します）。これで、2つの転置を選択する必要があることがわかりました。これらは、構成されると、単位元列になります。最初の場所に任意の要素を配置して、それを呼び出しましょう。上で述べたように、アイデンティティではないと仮定する可能性があります（すでに2つ配置しているため、アイデンティティではあり得ません）。 i = N - 2 = 2t1Mt1
I = _t1_ ___ _X_ _X_
M * ? * N * N
2番目のスポットに入る可能性のある残りの要素は、の逆数だけですt1。これは実際にt1あります（これは、逆数の一意性による唯一の要素です）。ここでも二項係数を含めます。この場合、4つのオープンロケーションがあり、2つのID順列を配置しようとしています。それを行う方法はいくつありますか？42を選択します。
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）。可能性はたくさんあるので、トリッキーになり始めます。二重に数えないように注意する必要があります。同様に、最初の場所に1つの要素を配置し、可能な組み合わせを検討することから始めます。最初に最も簡単な方法を取ります。同じ転置を4回行います。
I = _t1_ _t1_ _t1_ _t1_
M * 1 * 1 * 1 => M possibilities
t1ここで、2つの固有の要素とを考えてみましょうt2。Mの可能性と可能性t1のみがあります（に等しくすることはできないため）。すべての取り決めを使い果たすと、次のパターンが残ります。M-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
次に、3つの固有の要素、、、を考えてみましょt1う。最初に配置してから。いつものように、私たちは持っています：t2t3t1t2
I = _t1_ _t2_ ___ ___
M * ? * ? * ?
まだいくつの可能性があるかはまだわかりませんt2。その理由はすぐにわかります。
3番目の場所t1に配置します。t1最後の場所に行くとしたら、(3)rd上記の配置を再現するだけなので、そこに行かなければならないことに注意してください。ダブルカウントは悪いです！これにより、3番目の一意の要素t3が最終的な位置に残ります。
I = _t1_ _t2_ _t1_ _t3_
M * ? * 1 * ?
では、なぜt2sの数をより綿密に検討するために1分かかる必要があったのでしょうか。転置t1とは互いに素な順列にt2 することはできません（つまりn、またはの1つを共有する必要があります（また、等しくすることはできないため、1つだけを共有する必要がありますm）。これは、それらが互いに素である場合、順列の順序を入れ替えることができるためです。これは、(1)stアレンジメントを二重にカウントすることを意味します。
言うt1 = (n, m)。互いに素であるためには、形式または一部t2の形式である必要があります。またはではない場合があり、多くの場合はまたはではないことに注意してください。したがって、可能な順列の数は実際にはです。(n, x)(y, m)xyxnmynmt22 * (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にも等しくないことに注意してください。したがって、この場合、二重カウントはありません。t1t2
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）| 製品|
_________ | _________ | _____________ | _________ |
| | | | |
| i = 0 | 0.316 | 120/1296 | 0.029 |
| _________ | _________ | _____________ | _________ |
| | | | |
| i = 2 | 0.211 | 6/36 | 0.035 |
| _________ | _________ | _____________ | _________ |
| | | | |
| i = 4 | 0.004 | 1/1 | 0.004 |
| _________ | _________ | _____________ | _________ |
| | |
| 合計：| 0.068 |
| _____________ | _________ |
ここに適用する群論の結果があったら、それはクールだろう-そして多分あるだろう！それは確かに、この退屈なカウントをすべて完全になくすのに役立ちます（そして問題をはるかにエレガントなものに短縮します）。で仕事をやめましたN = 4。の場合N > 5、与えられたものは概算を与えるだけです（どれだけ良いかはわかりません）。それを考えると、その理由はかなり明らかです。たとえば、転置が与えられた場合、上記で説明されていない4つの固有の要素を使用N = 8してアイデンティティを作成する方法が明らかにあります。順列が長くなるにつれて、方法の数を数えるのが一見難しくなります（私が知る限り...）。
とにかく、インタビューの範囲内でこのようなことは絶対にできませんでした。運が良ければ、分母のステップまで到達できます。それを超えて、それはかなり厄介なようです。
なぜこれらの人々が確率についてそれほど奇妙な質問をするのか知りたいのですが？
このような質問は、インタビュアーがインタビュイーの洞察を得ることができるために尋ねられます
... 等々。インタビュイーのこれらの属性を明らかにする質問をするための鍵は、一見単純なコードを用意することです。これは、非コーダーが立ち往生している詐欺師を振り払います。傲慢な人は間違った結論に飛びつきます。怠惰な、または標準以下のコンピューター科学者は、簡単な解決策を見つけて、探すのをやめます。多くの場合、彼らが言うように、それはあなたが正しい答えを得るかどうかではなく、あなたがあなたの思考プロセスに感銘を与えるかどうかです。
私も質問に答えようとします。面接では、一行で答えるのではなく、自分自身を説明したいと思います。これは、「答え」が間違っていても、論理的思考を示すことができるためです。
Aは同じままです-つまり、同じ位置にある要素-
m == nすべての反復で（すべての要素がそれ自体とのみスワップするように）。また最初のケースは、duedl0rが提供する「単純な」ケースであり、配列が変更されていない場合です。これが答えかもしれません、なぜなら
配列Aが同じままである確率はどれくらいですか？
配列がで変更されてから元i = 1に戻る場合i = 2、元の状態にありますが、「同じままではありません」-変更されてから元に戻されます。それは賢い技術かもしれません。
次に、要素が交換されたり、元に戻されたりする可能性を考えると、インタビューでは計算が頭上にあると思います。明らかな考慮事項は、それが変更である必要はないということです。スワップを元に戻すと、1と2、次に2と3、1と3、最後に2と3の3つの要素間で同じように簡単にスワップできます。続けて、このように「循環」している4、5、またはそれ以上のアイテム間でスワップが発生する可能性があります。
実際、配列が変更されていない場合を考慮するよりも、配列が変更されている場合を考慮する方が簡単な場合があります。この問題をパスカルの三角形のような既知の構造にマッピングできるかどうかを検討してください。
これは難しい問題です。面接で解決するのが難しすぎるということには同意しますが、それは面接で質問するのが難しすぎるという意味ではありません。貧しい候補者には答えがなく、平均的な候補者は明白な答えを推測し、良い候補者は問題が答えるのが難しすぎる理由を説明します。
これは、面接官に候補者への洞察を与える「自由形式の」質問だと思います。このため、面接で解決するのは難しいですが、面接で質問するのは良い質問です。答えが正しいか間違っているかを確認するだけでなく、質問をすることも重要です。
以下は、randが生成できるインデックスの2Nタプルの値の数をカウントし、確率を計算するためのCコードです。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;
}
アルゴリズムの動作は、対称群SN上のマルコフ連鎖としてモデル化できます。
配列のN個の要素はNAに配置できます！さまざまな順列。これらの順列に1からN！までの番号を付けましょう。たとえば、辞書式順序で番号を付けます。したがって、アルゴリズムの任意の時点での配列の状態は、順列番号によって完全に特徴付けることができます。A
たとえば、N = 3の場合、3つすべての1つの可能な番号付け！=6つの順列は次のようになります。
アルゴリズムの各ステップで、状態はA同じままであるか、これらの順列の1つから別の順列に遷移します。現在、これらの状態変化の確率に関心があります。単一のループ反復で状態が順列iから順列jに変化する確率をPr（i → j）と呼びましょう。
mとnを[0、 N -1]の範囲から均一かつ独立して選択すると、 N²の可能な結果があり、それぞれが同じように発生する可能性があります。
これらの結果のNについては、 m = nが成り立つため、順列に変化はありません。したがって、
。
残りのN²- Nの場合は転置です。つまり、2つの要素が位置を交換するため、順列が変化します。これらの転置の1つが位置xとyの要素を交換するとします。この転置をアルゴリズムで生成する方法は2つあります。m=x、n=yまたはm=y、n=xのいずれかです。したがって、各転置の確率は2/ N²です。
これは私たちの順列とどのように関係していますか？iをjに変換する（およびその逆の）転置がある場合にのみ、 2つの順列を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は、順列iで開始したと仮定して、Nステップ後に順列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回数字を描いています。それらのいずれかが一意である場合（1回だけ発生する場合）、要素が消えて元の場所に戻ることができないため、配列は確実に変更されます。
固定数が一意である確率は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）を意味します。残念ながら、それらは独立していません。より洗練された分析で限界を示すことができると思います。キーワードは「ボールとビンの問題」です。
単純な解決策の1つは
p> = 1 / N N
配列が同じままである1つの可能な方法は、m = nすべての反復の場合です。そして可能性とm等しい。n1 / N
それは確かにそれよりも高いです。問題は、いくらかです。
2番目の考え：配列をランダムにシャッフルすると、すべての順列の確率が等しくなると主張することもできます。順列があるのでn!、1つだけ（最初に持っているもの）を取得する確率は
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)
説明：元の配列を取得するには、2つの方法があります。すでに良い配列で「中立」の移調を行うか、唯一の「悪い」移調を元に戻すことです。「不良」転置が1つしかない配列を取得するには、不良転置が0の配列を取得し、ニュートラルではない1つの転置を作成します。
編集：P（n-1,0）の-1ではなく-2
これは完全な解決策ではありませんが、少なくとも何かです。
効果のない特定のスワップのセットを取ります。スワップの合計を使用して、nスワップがさまざまなサイズのループの束を形成することになったのは事実だったに違いありません。（この目的のために、効果のないスワップはサイズ1のループと見なすことができます）
おそらく私たちはできる
1）ループのサイズに基づいてそれらをグループに分割します
。2）各グループを取得する方法の数を計算します。
（主な問題は、さまざまなグループがたくさんあることですが、さまざまなグループを考慮しない場合、実際にこれをどのように計算するかはわかりません。）
興味深い質問です。
答えは1/Nだと思いますが、証拠がありません。証拠を見つけたら、答えを編集します。
私が今まで得たもの：
m == nの場合、配列は変更されません。n ^ 2のオプションがあり、Nのみが適切であるため（0 <= i <= N-1ごとに（i、i））、m==nを取得する確率は1/Nです。
したがって、N / N ^ 2 = 1/Nが得られます。
スワップをk回繰り返した後、サイズNの配列が同じままになる確率をPkに示します。
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の場合、2番目は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.
編集： 私は別のアプローチを紹介したい：
スワップは、建設的スワップ、破壊的スワップ、無害スワップの3つのグループに分類できます。
建設的スワップは、少なくとも1つの要素を適切な場所に移動させるスワップとして定義されます。
破壊的スワップは、少なくとも1つの要素を正しい位置から移動させるスワップとして定義されます。
無害なスワップは、他のグループに属していないスワップとして定義されています。
これがすべての可能なスワップのパーティションであることは簡単にわかります。（交差=空のセット）。
今私が証明したい主張：
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）を取ります。そして、すべての可能性を見てください。
ノードが配列の要素であり、スワップがそれらの間に無向（！）接続を追加するマルチグラフとして問題をモデル化します。次に、何らかの方法でループを探します（すべてのノードはループの一部です=>元の）
本当に仕事に戻る必要があります！:(
まあ、数学的な観点から：
配列要素を毎回同じ場所で交換するには、Rand（N）関数がintmとintnに対して同じ数を2回生成する必要があります。したがって、Rand（N）関数が同じ数を2回生成する確率は1/Nです。そして、forループ内でRand（N）がN回呼び出されるため、確率は1 /（N ^ 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;
}
}
}
質問：アレイ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だと思います。