_{Eh bien, je me suis amusé un peu avec celui-ci. La première chose à laquelle j’ai pensé lorsque j’ai lu le problème pour la première fois était la théorie des groupes (le groupe symésortingque S n , en particulier). La boucle for construit simplement une permutation σ dans S n en composant des transpositions (c.-à-d. Des swaps) à chaque itération. Mes maths ne sont pas si spectaculaires et je suis un peu rouillé, alors si ma notation est en panne avec moi.}

---

Vue d’ensemble

Soit A l’événement que notre tableau est inchangé après permutation. On nous demande finalement de trouver la probabilité de l’événement A , Pr(A) .

Ma solution tente de suivre la procédure suivante:

1. Considérer toutes les permutations possibles (c.-à-d. Les réordonnances de notre tableau)
2. Partitionnez ces permutations en ensembles disjoints en fonction du nombre de transpositions identitaires qu’ils contiennent. Cela permet de réduire le problème à des permutations égales.
3. Déterminer la probabilité d’obtenir la permutation d’identité étant donné que la permutation est paire (et d’une longueur particulière).
4. Sommez ces probabilités pour obtenir la probabilité globale que le tableau rest inchangé.

1) Résultats possibles

Notez que chaque itération de la boucle for crée un échange (ou une transposition ) qui résulte de l’une des deux choses suivantes (mais jamais les deux):

1. Deux éléments sont échangés.
2. Un élément est échangé avec lui-même. Pour nos fins et objectives, le tableau est inchangé.

Nous étiquetons le deuxième cas. Définissons une transposition d’identité comme suit:

Une transposition d’identité se produit lorsqu’un numéro est échangé avec lui-même. C’est-à-dire lorsque n == m dans la boucle ci-dessus.

Pour toute exécution du code répertorié, nous composons N transpositions. Il peut y avoir 0, 1, 2, ... , N des transpositions d’identité apparaissant dans cette “chaîne”.

---

Par exemple, considérons un cas 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 ** 

Notez qu’il existe un nombre impair de transpositions de non-identité (1) et que le tableau est modifié.

---

2) Partitionnement basé sur le nombre de transpositions d’identité

Soit K_i l’événement où les transpositions d’identité apparaissent dans une permutation donnée. Notez que cela forme une partition exhaustive de tous les résultats possibles:

• Aucune permutation ne peut avoir deux quantités différentes de transpositions d’identité simultanément, et
• Toutes les permutations possibles doivent avoir entre 0 et N transpositions d’identité.

Ainsi, nous pouvons appliquer la loi de la probabilité totale :

Maintenant, nous pouvons enfin profiter de la partition. Notez que lorsque le nombre de transpositions sans identité est impair, il est impossible que le tableau rest inchangé *. Ainsi:

* _{De la théorie des groupes, une permutation est paire ou impaire mais jamais les deux. Par conséquent, une permutation impaire ne peut pas être la permutation d’identité (puisque la permutation d’identité est paire).}

3) Déterminer les probabilités

Nous devons donc maintenant déterminer deux probabilités pour Ni même:

1. 
2. 

Le premier terme

Le premier terme, , représente la probabilité d’obtenir une permutation avec des transpositions d’identité. Cela s’avère être un binôme puisque pour chaque itération de la boucle for:

• Le résultat est indépendant des résultats avant
• La probabilité de créer une transposition d’identité est la même, à savoir 1/N

Ainsi, pour les essais N , la probabilité d’obtenir des transpositions d’identité est la suivante:

Le second terme

Donc, si vous êtes arrivé si loin, nous avons réduit le problème à trouver pour N - i même. Ceci représente la probabilité d’obtenir une permutation d’identité étant donné que les transpositions sont des identités. J’utilise une approche de comptage naïve pour déterminer le nombre de façons de réaliser la permutation d’identité sur le nombre de permutations possibles.

Considérons d’abord les permutations (n, m) et (m, n) équivalentes. Soit M le nombre de permutations non identitaires possibles. Nous utiliserons cette quantité fréquemment.

Le but ici est de déterminer le nombre de façons dont un ensemble de transpositions peut être combiné pour former la permutation d’identité. Je vais essayer de construire la solution générale à côté d’un exemple de N = 4 .

---

Considérons le cas N = 4 avec toutes les transpositions d’identité ( ie i = N = 4 ). Soit X une transposition d’identité. Pour chaque X , il y a N possibilités (elles sont: n = m = 0, 1, 2, ... , N - 1 ). Il y a donc N^i = 4^4 possibilités pour réaliser la permutation d’identité. Pour être complet, nous ajoutons le coefficient binomial, C(N, i) , pour considérer l’ordre des transpositions d’identité (ici, il est égal à 1). J’ai essayé de décrire ci-dessous la disposition physique des éléments ci-dessus et le nombre de possibilités ci-dessous:

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

Maintenant, sans substituer explicitement N = 4 et i = 4 , nous pouvons examiner le cas général. En combinant ce qui précède avec le dénominateur trouvé précédemment, on trouve:

Ceci est intuitif. En fait, toute autre valeur que 1 devrait probablement vous alarmer. Pensez-y: on nous donne la situation dans laquelle toutes les transpositions N sont dites identitaires. Quelle est la probabilité que le tableau rest inchangé dans cette situation? Clairement, 1 .

---

Maintenant, encore une fois pour N = 4 , considérons 2 transpositions d’identité ( ie i = N - 2 = 2 ). En guise de convention, nous placerons les deux identités à la fin (et le compte pour les commandes ultérieures). Nous soaps maintenant que nous devons choisir deux transpositions qui, une fois composées, deviendront la permutation d’identité. Placez n’importe quel élément au premier emplacement, appelez-le t1 . Comme indiqué ci-dessus, il existe M possibilités en supposant que t1 ne soit pas une identité (cela ne peut pas être comme nous en avons déjà placé deux).

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

Le seul élément restant qui pourrait éventuellement entrer dans le deuxième spot est l’inverse de t1 , qui est en fait t1 (et c’est le seul par l’unicité de l’inverse). Nous incluons à nouveau le coefficient binomial: dans ce cas, nous avons 4 emplacements ouverts et nous cherchons à placer 2 permutations d’identité. Combien de façons pouvons-nous faire? 4 choisissez 2.

 I = _t1_ _t1_ _X_ _X_ M * 1 * N * N * C(4, 2) => C(N, N-2) * M * N^(N-2) possibilities 

Toujours en regardant le cas général, tout cela correspond à:

---

Enfin, nous faisons le cas N = 4 sans transpositions d’identité ( ie i = N - 4 = 0 ). Comme il y a beaucoup de possibilités, cela commence à devenir difficile et nous devons faire attention à ne pas doubler. Nous commençons de la même manière en plaçant un seul élément au premier rang et en élaborant des combinaisons possibles. Prenez d’abord le plus simple: la même transposition 4 fois.

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

Considérons maintenant deux éléments uniques t1 et t2 . Il y a M possibilités pour t1 et seulement M-1 pour t2 (puisque t2 ne peut pas être égal à t1 ). Si nous épuisons tous les arrangements, nous nous retrouvons avec les modèles suivants:

 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 

Considérons maintenant trois éléments uniques, t1 , t2 , t3 . Plaçons d’abord t1 puis t2 . Comme d’habitude, nous avons:

 I = _t1_ _t2_ ___ ___ M * ? * ? * ? 

Nous ne pouvons pas encore dire combien de t2 possibles il peut encore y avoir, et nous verrons pourquoi dans une minute.

Nous t1 maintenant t1 à la troisième place. Remarquez que t1 doit y aller car si nous devions aller au dernier rang, nous ne ferions que recréer la (3)rd disposition ci-dessus. Le double comptage est mauvais! Cela laisse le troisième élément unique t3 à la position finale.

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

Alors, pourquoi avons-nous dû prendre une minute pour examiner le nombre de t2 plus près? Les transpositions t1 et t2 ne peuvent pas être des permutations disjointes ( c’est-à-dire qu’elles doivent en partager une (et une seule car elles ne peuvent pas non plus être égales) de leur n ou m ). La raison en est que si elles étaient disjointes, nous pourrions échanger l’ordre des permutations. Cela signifie que nous compterions le (1)st arrangement.

Dites t1 = (n, m) . t2 doit être de la forme (n, x) ou (y, m) pour certains x et y afin d’être non disjoint. Notez que x peut ne pas être n ou m et y beaucoup ne sont pas n ou m . Ainsi, le nombre de permutations possibles que t2 pourrait être est en fait de 2 * (N - 2) .

Donc, revenons à notre mise en page:

 I = _t1_ _t2_ _t1_ _t3_ M * 2(N-2) * 1 * ? 

Maintenant, t3 doit être l’inverse de la composition de t1 t2 t1 . Faisons-le manuellement:

 (n, m)(n, x)(n, m) = (m, x) 

Ainsi, t3 doit être (m, x) . Notez que ce n’est pas disjoint pour t1 et n’est pas égal à t1 ou t2 donc il n’y a pas de double compte pour ce cas.

 I = _t1_ _t2_ _t1_ _t3_ M * 2(N-2) * 1 * 1 => M * 2(N - 2) possibilities 

Enfin, en mettant tout cela ensemble:

---

4) Tout rassembler

Alors c’est tout. Travaillez en arrière, en substituant ce que nous avons trouvé à la sum initiale donnée à l’étape 2. J’ai calculé la réponse à la casse N = 4 ci-dessous. Il correspond très étroitement au nombre empirique trouvé dans une autre réponse!

          N = 4
          M = 6 _________ _____________ _________
                   |  Pr (K_i) |  Pr (A | K_i) |  Produit | 
          _________ | _________ | _____________ | _________ |
         |  |  |  |  |
         |  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 |
                             | _____________ | _________ |

Exactitude

Ce serait cool s’il y avait un résultat dans la théorie du groupe à appliquer ici– et peut-être qu’il y en a! Cela aiderait certainement à faire disparaître complètement ce comptage fastidieux (et à réduire le problème à quelque chose de beaucoup plus élégant). J’ai arrêté de travailler à N = 4 . Pour N > 5 , ce qui est donné ne donne qu’une approximation (comme je ne suis pas sûr). Il est assez clair que cela se produise si vous y réfléchissez: par exemple, avec N = 8 transpositions, il existe clairement des moyens de créer l’identité avec quatre éléments uniques qui ne sont pas pris en compte ci-dessus. Le nombre de façons devient apparemment plus difficile à compter, car la permutation s’allonge (pour autant que je sache…).

Quoi qu’il en soit, je ne pouvais absolument pas faire quelque chose comme ça dans le cadre d’une interview. J’arriverais à l’étape du dénominateur si j’avais de la chance. Au-delà, ça semble plutôt méchant.

Très curieux de savoir pourquoi ces personnes posent des questions si étranges sur la probabilité?

Des questions comme celle-ci sont posées parce qu’elles permettent à l’intervieweur de mieux comprendre

• capacité à lire le code (code très simple mais au moins quelque chose)
• pouvoir parsingr un algorithme pour identifier le chemin d’exécution
• compétences à appliquer la logique pour trouver des résultats possibles
• le raisonnement et la résolution de problèmes en travaillant sur le problème
• compétences en matière de communication et de travail – posent-ils des questions ou travaillent-ils en vase clos sur la base d’informations disponibles?

… etc. La clé pour avoir une question qui expose ces atsortingbuts de l’interviewé est d’avoir un morceau de code d’une simplicité trompeuse. Cela secoue les imposteurs que le non-codeur est bloqué; l’arrogant saute à la mauvaise conclusion; l’informaticien paresseux ou sub-parat trouve une solution simple et arrête de chercher. Souvent, comme on dit, ce n’est pas si vous obtenez la bonne réponse, mais si vous êtes impressionné par votre processus de reflection.

---

Je vais essayer de répondre à la question aussi. Dans une interview, je m’expliquerais plutôt que de fournir une réponse écrite à une ligne, car même si ma «réponse» est erronée, je suis capable de faire preuve de logique.

A restra le même – c.-à-d. Des éléments dans les mêmes positions – quand

• m == n à chaque itération (pour que chaque élément ne change que lui-même); ou
• tout élément qui est échangé est replacé dans sa position d’origine

Le premier cas est le cas «simple» que duedl0r donne, le cas où le tableau n’est pas modifié. Cela pourrait être la réponse, car

Quelle est la probabilité que le tableau A rest le même?

Si le tableau change à i = 1 , puis revient à i = 2 , il est dans l’état d’origine mais il n’est pas resté le même – il a été modifié, puis il a été modifié. Cela pourrait être une technicité smartass.

Puis, en considérant la possibilité que des éléments soient échangés et échangés – je pense que ce calcul est au-dessus de ma tête dans une interview. La considération évidente est que cela n’a pas besoin d’être un changement – changez le swap, il pourrait tout aussi bien y avoir un échange entre trois éléments, en échangeant 1 et 2, puis 2 et 3, 1 et 3 et enfin 2 et 3. Et En continuant, il pourrait y avoir des swaps entre 4, 5 articles ou plus qui sont «circulaires» comme celui-ci.

En fait, plutôt que de considérer les cas où le tableau est inchangé, il peut être plus simple de considérer les cas où il est modifié. Déterminez si ce problème peut être associé à une structure connue telle que le sortingangle de Pascal .

---

C’est un problème difficile. Je suis d’accord que c’est trop difficile à résoudre dans une interview, mais cela ne veut pas dire que c’est trop difficile à demander lors d’une interview. Le pauvre candidat n’aura pas de réponse, le candidat moyen devinera la réponse évidente et le bon candidat expliquera pourquoi le problème est trop difficile à répondre.

Je considère que c’est une question «ouverte» qui donne à l’enquêteur un aperçu du candidat. Pour cette raison, même si cela est trop difficile à résoudre lors d’une interview, c’est une bonne question à poser lors d’une interview. Il y a plus à poser une question qu’à vérifier si la réponse est correcte ou non.

Ci-dessous, le code C permet de compter le nombre de valeurs du double indice d’indices que rand peut produire et de calculer la probabilité. À partir de N = 0, il affiche les nombres de 1, 1, 8, 135, 4480, 189125 et 12450816, avec des probabilités de 1, 1, .5, .185185, .0683594, .0193664 et .00571983. Les comptes n’apparaissent pas dans l’ Encyclopedia of Integer Sequence , donc mon programme a un bug ou c’est un problème très obscur. Si tel est le cas, le demandeur n’a pas l’intention de résoudre le problème, mais d’exposer certains de ses processus de reflection et la manière dont ils traitent la frustration. Je ne considérerais pas cela comme un bon problème d’entretien.

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

Le comportement de l’algorithme peut être modélisé comme une chaîne de Markov sur le groupe symésortingque S _N.

Les bases

Les N éléments du tableau A peuvent être disposés en N ! différentes permutations. Numérotons ces permutations de 1 à N !, Par exemple par ordre lexicographique. Ainsi, l’état du tableau A à tout moment dans l’algorithme peut être entièrement caractérisé par le nombre de permutation.

Par exemple, pour N = 3, une numérotation possible des trois! = 6 permutations pourraient être:

1. abc
2. acb
3. bac
4. bca
5. taxi
6. cba

Probabilités de transition d’état

A chaque étape de l’algorithme, l’état de A rest le même ou passe d’une de ces permutations à une autre. Nous nous intéressons maintenant aux probabilités de ces changements d’état. Appelons Pr ( i → j ) la probabilité que l’état passe de la permutation i à la permutation j dans une itération en boucle unique.

Comme nous choisissons m et n uniformément et indépendamment de la plage [0, N -1], il existe N ² résultats possibles, chacun étant également probable.

Identité

Pour N de ces résultats, m = n est valable, il n’y a donc pas de changement dans la permutation. Donc,

.

Transpositions

Les cas N ² – N restants sont des transpositions, c’est-à-dire que deux éléments échangent leurs positions et donc la permutation change. Supposons qu’une de ces transpositions échange les éléments aux positions x et y . Il existe deux cas dans lesquels cette transposition peut être générée par l’algorithme: m = x , n = y ou m = y , n = x . Ainsi, la probabilité pour chaque transposition est de 2 / N².

Comment cela se rapporte-t-il à nos permutations? Appelons deux permutations i et j voisines si et seulement si il y a une transposition qui transforme i en j (et vice versa). Nous pouvons alors conclure:

Masortingce de transition

On peut organiser les probabilités Pr ( i → j ) dans une masortingce de transition P ∈ [0,1] ^{N ! × N !} . Nous définissons

p _ij = Pr ( i → j )

où p _ij est l’entrée dans la iième ligne et la jième colonne de P. Notez que

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

ce qui signifie que P est symésortingque.

Le point clé maintenant est l’observation de ce qui se passe lorsque nous multiplions P par lui-même. Prenez n’importe quel élément p ⁽²⁾ _ij de P²:

Le produit Pr ( i → k ) · Pr ( k → j ) est la probabilité que, à partir de la permutation i, nous passons en permutation k en une étape et que nous passions en permutation j après une autre étape ultérieure. La sum de toutes les permutations intermédiaires k nous donne donc la probabilité totale de passer de i à j en 2 étapes .

Cet argument peut être étendu à des puissances plus élevées de P. Une conséquence particulière est la suivante:

p ^{( N )} _ii est la probabilité de revenir à la permutation i après N étapes, en supposant que nous avons commencé à la permutation i .

Exemple

Jouons ceci avec N = 3. Nous avons déjà une numérotation pour les permutations. La masortingce de transition correspondante est la suivante:

En multipliant P par lui-même, on obtient:

Une autre multiplication donne:

Tout élément de la diagonale principale nous donne la probabilité recherchée, qui est _15/81 ou _5/27 .

Discussion

Bien que cette approche soit mathématiquement valable et puisse être appliquée à toute valeur de N , elle n’est pas très pratique sous cette forme. La masortingce de transition P a N ! ², ce qui devient très rapide. Même pour N = 10, la taille de la masortingce dépasse déjà 13 000 milliards d’entrées. Une implémentation naïve de cet algorithme apparaît donc impossible.

Cependant, par rapport à d’autres propositions, cette approche est très structurée et ne nécessite pas de dérivations complexes au-delà de la détermination des permutations qui sont voisines. J’espère que cette structure pourra être exploitée pour trouver un calcul beaucoup plus simple.

Par exemple, on pourrait exploiter le fait que tous les éléments diagonaux de toute puissance de P sont égaux. En supposant que nous pouvons facilement calculer la trace de P ^N , la solution est alors tout simplement tr ( P ^N ) / N !. La trace de P ^N est égale à la sum des N- puissances de ses valeurs propres. Donc, si nous avions un algorithme efficace pour calculer les valeurs propres de P , nous serions définis. Je n’ai pas exploré cela plus loin que le calcul des valeurs propres jusqu’à N = 5, cependant.

Il est facile d’observer des limites 1 / n ⁿ <= p <= 1 / n.

Voici une idée incomplète de montrer une limite supérieure inverse-exponentielle.

Vous dessinez des nombres de {1,2, .., n} 2n fois. Si l’un d’entre eux est unique (se produit exactement une fois), le tableau sera définitivement modifié, car l’élément est parti et ne peut pas revenir à son emplacement d’origine.

La probabilité qu’un nombre fixe soit unique est de 2n * 1 / n * (1-1 / n) ^ (2n-1) = 2 * (1-1 / n) ^ (2n-1) qui est de manière asymésortingque 2 / e ² , borné par 0. [2n parce que vous choisissez sur quel essai vous l’obtenez, 1 / n que vous avez eu sur cet essai, (1-1 / n) ^ (2n-1) que vous ne l’avez pas obtenu autres essais]

Si les événements étaient indépendants, vous auriez cette chance que tous les nombres ne soient pas uniques: (2 / e ² ) ^ n, ce qui signifierait p <= O ((2 / e ² ) ^ n). Malheureusement, ils ne sont pas indépendants. Je pense que le lien peut être montré avec une parsing plus sophistiquée. Le mot-clé est “problème des boules et des poubelles”.

Une solution simpliste est

p> = 1 / N ^N

Une des manières possibles étant que le tableau rest le même est si m = n pour chaque itération. Et m est égal à n avec possibilité 1 / N

C’est certainement plus que ça. La question est de savoir combien..

Deuxième pensée: On pourrait aussi argumenter que si vous mélangez un tableau de manière aléatoire, chaque permutation a la même probabilité. Depuis il y a n! permutations la probabilité d’obtenir juste un (celui que nous avons au début) est

p = 1 / N!

ce qui est un peu mieux que le résultat précédent.

Comme discuté, l’algorithme est biaisé. Cela signifie que toutes les permutations n’ont pas la même probabilité. Donc 1 / N! n’est pas tout à fait exact. Vous devez savoir comment se répartissent les permutations.

FYI, pas sûr que la limite ci-dessus (1 / n ^ 2) soit valide:

 N=5 -> 0.019648 < 1/25 N=6 -> 0.005716 < 1/36 

Code d'échantillonnage:

 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) 

Tout le monde suppose que A[i] == i , qui n’était pas explicitement indiqué. Je vais faire cette hypothèse aussi, mais notez que la probabilité dépend du contenu. Par exemple si A[i]=0 , alors la probabilité = 1 pour tout N.

Voici comment le faire. Soit P(n,i) la probabilité que le tableau résultant diffère exactement par les transpositions du tableau d’origine.

Nous voulons savoir P(n,0) . C’est vrai que:

 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) 

Explication: on peut obtenir le tableau original de deux manières, soit en effectuant une transposition “neutre” dans un tableau déjà bon, soit en inversant la seule “mauvaise” transposition. Pour obtenir un tableau avec une seule “mauvaise” transposition, nous pouvons prendre un tableau avec 0 mauvaises transpositions et effectuer une transposition non neutre.

EDIT: -2 ​​au lieu de -1 dans P (n-1,0)

Ce n’est pas une solution complète, mais c’est quelque chose au moins.

Prenez un ensemble particulier de swaps sans effet. Nous soaps que ses swaps ont dû former un groupe de boucles de différentes tailles, en utilisant un total de n swaps. (Aux fins de ceci, un échange sans effet peut être considéré comme une boucle de taille 1)

Peut-être pouvons-nous

1) Décomposez-les en groupes en fonction de la taille des boucles
2) Calculez le nombre de façons d’obtenir chaque groupe.

(Le problème principal est qu’il ya une tonne de groupes différents, mais je ne suis pas sûr de savoir comment vous pourriez calculer cela si vous ne tenez pas compte des différents groupes.)

Question interessante.

Je pense que la réponse est 1 / N, mais je n’ai aucune preuve. Quand je trouve une preuve, je vais éditer ma réponse.

Ce que j’ai eu jusqu’à maintenant:

Si m == n, vous ne modifierez pas le tableau. La probabilité d’obtenir m == n est 1 / N, car il y a N ^ 2 options, et seul N convient ((i, i) pour tout 0 <= i <= N-1).

On obtient donc N / N ^ 2 = 1 / N.

Soit Pk la probabilité qu’après k itérations de swaps, le tableau de taille N rest le même.

P1 = 1 / N. (Comme nous l’avons vu ci-dessous)

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.

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! 🙁

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)

Naive implementation in C#. The idea is to create all the possible permutations of initial array and enumerate them. Then we build a masortingx of possible changes of state. Multiplying masortingx by itself N times we will get the masortingx 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(ssortingng[] args) { for (int i = 1; i < 7; i++) { MainClass mc = new MainClass(i); mc.Run(); } } } class MainClass { int N; int M; List comb; List lastItemIdx; public List> combinations; int[,] masortingx; public MainClass(int n) { N = n; comb = new List(); lastItemIdx = new List(); for (int i = 0; i < n; i++) { comb.Add(-1); lastItemIdx.Add(-1); } combinations = new List>(); } public void Run() { GenerateAllCombinations(); GenerateMasortingx(); int[,] m2 = masortingx; 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(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; } } } 

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.

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

Sortie de l'échantillon:

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