algorithm - utero - remedios caseros para matriz infantil

¿Cuál es la probabilidad de que la matriz se mantenga igual?

Question

Esta pregunta ha sido formulada en una entrevista de Microsoft. ¿Es muy curioso saber por qué estas personas hacen preguntas tan extrañas sobre la probabilidad?

Dado un rand (N), un generador aleatorio que genera un número aleatorio de 0 a 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]);
}

EDITAR: Tenga en cuenta que la semilla no es fija.

¿Cuál es la probabilidad de que la matriz A siga siendo la misma?
Suponga que la matriz contiene elementos únicos.

Answer 1

¿Es muy curioso saber por qué estas personas hacen preguntas tan extrañas sobre la probabilidad?

Se hacen preguntas como esta porque permiten que el entrevistador obtenga una idea de lo que el entrevistado

• código de lectura de habilidad (código muy simple pero al menos algo)
• capacidad de analizar un algoritmo para identificar la ruta de ejecución
• habilidades para aplicar la lógica para encontrar posibles resultados y caso límite
• razonamiento y habilidades para resolver problemas a medida que trabajan a través del problema
• habilidades de comunicación y trabajo: ¿hacen preguntas o trabajan de forma aislada según la información disponible?

... y así. La clave para tener una pregunta que expone estos atributos del entrevistado es tener una pieza de código engañosamente simple. Esto sacude a los impostores que el no codificador está estancado; el arrogante salto a la conclusión equivocada; el científico informático perezoso o por debajo de lo común encuentra una solución simple y deja de buscar. A menudo, como dicen, no se trata de obtener la respuesta correcta, sino de si impresionas con tu proceso de pensamiento.

Voy a intentar responder la pregunta, también. En una entrevista me explicaría a mí mismo en lugar de proporcionar una respuesta escrita de una sola línea, esto es porque incluso si mi ''respuesta'' es incorrecta, puedo demostrar el pensamiento lógico.

A seguirá siendo el mismo, es decir, elementos en las mismas posiciones, cuando

• m == n en cada iteración (para que cada elemento solo intercambie consigo mismo); o
• cualquier elemento que se intercambie se intercambia a su posición original

El primer caso es el caso ''simple'' que otorga duedl0r, el caso de que la matriz no se modifique. Esta podría ser la respuesta, porque

¿Cuál es la probabilidad de que la matriz A siga siendo la misma?

si la matriz cambia en i = 1 y luego vuelve a i = 2 , está en el estado original pero no "sigue siendo la misma" - se cambió y luego se cambió nuevamente. Eso podría ser un tecnicismo de smartass.

Luego, considerando la posibilidad de que los elementos se intercambien y se intercambien, creo que el cálculo está por encima de mi cabeza en una entrevista. La consideración obvia es que eso no necesita ser un cambio, cambio de devolución, podría haber un intercambio entre tres elementos, intercambiando 1 y 2, luego 2 y 3, 1 y 3 y finalmente 2 y 3. Y continuando, podría haber intercambios entre 4, 5 o más elementos que son ''circulares'' como este.

De hecho, en lugar de considerar los casos en los que la matriz no ha cambiado, puede ser más simple considerar los casos en los que se cambia. Considere si este problema puede mapearse en una estructura conocida como el triángulo de Pascal .

Es este un problema difícil. Estoy de acuerdo en que es muy difícil de resolver en una entrevista, pero eso no significa que sea demasiado difícil de preguntar en una entrevista. El candidato pobre no tendrá una respuesta, el candidato promedio adivinará la respuesta obvia, y el buen candidato explicará por qué el problema es demasiado difícil de responder.

Considero que esta es una pregunta ''abierta'' que le da al entrevistador una idea del candidato. Por esta razón, aunque es muy difícil de resolver durante una entrevista, es una buena pregunta que hacer durante una entrevista. Hay más para hacer una pregunta que simplemente verificar si la respuesta es correcta o incorrecta.

Answer 2

A continuación se muestra el código C para contar el número de valores de la 2N-tupla de los índices que rand puede producir y calcular la probabilidad. Comenzando con N = 0, muestra recuentos de 1, 1, 8, 135, 4480, 189125 y 12450816, con probabilidades de 1, 1, .5, .185185, .0683594, .0193664 y .00571983. Los recuentos no aparecen en la Enciclopedia de secuencias enteras , por lo tanto, mi programa tiene un error o este es un problema muy oscuro. Si es así, el problema no está destinado a ser resuelto por un solicitante de empleo, sino para exponer algunos de sus procesos de pensamiento y cómo se enfrentan a la frustración. No lo consideraría un buen problema para la entrevista.

#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 3

El comportamiento del algoritmo se puede modelar como una cadena de Markov sobre el grupo simétrico S _N.

Lo esencial

Los N elementos de la matriz A pueden organizarse en N ! diferentes permutaciones. Vamos a numerar estas permutaciones de 1 a N !, Por ejemplo, por orden lexicográfico. De modo que el estado de la matriz A en cualquier momento en el algoritmo puede caracterizarse completamente por el número de permutación.

Por ejemplo, para N = 3, una numeración posible de los 3! = 6 permutaciones pueden ser:

1. a B C
2. acb
3. bac
4. bca
5. taxi
6. cba

Probabilidades de transición del estado

En cada paso del algoritmo, el estado de A mantiene igual o pasa de una de estas permutaciones a otra. Ahora estamos interesados ​​en las probabilidades de estos cambios de estado. Llamemos a Pr ( i → j ) la probabilidad de que el estado cambie de la permutación i a la permutación j en una iteración de bucle único.

Como seleccionamos myn uniformemente e independientemente del rango [0, N -1], hay N ² resultados posibles, cada uno de los cuales es igualmente probable.

Identidad

Para N de estos resultados m = n se cumple, por lo que no hay cambio en la permutación. Por lo tanto,

.

Transposiciones

Los casos N ² - N restantes son transposiciones, es decir, dos elementos intercambian sus posiciones y, por lo tanto, la permutación cambia. Supongamos que una de estas transposiciones intercambia los elementos en las posiciones x e y . Hay dos casos en los que el algoritmo puede generar esta transposición: o m = x , n = y o m = y , n = x . Por lo tanto, la probabilidad de cada transposición es 2 / N ².

¿Cómo se relaciona esto con nuestras permutaciones? Llamemos a dos permutaciones i y j vecinos si y solo si hay una transposición que transforma i en j (y viceversa). Entonces podemos concluir:

Matriz de transición

Podemos organizar las probabilidades Pr ( i → j ) en una matriz de transición P ∈ [0,1] ^{N ! × N !} . Definimos

p _ij = Pr ( i → j ),

donde p _ij es la entrada en la i -ésima fila y la j -ésima columna de P. Tenga en cuenta que

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

lo que significa que P es simétrico.

El punto clave ahora es la observación de lo que sucede cuando multiplicamos P por sí mismo. Tome cualquier elemento p ⁽²⁾ _ij de P ²:

El producto Pr ( i → k ) · Pr ( k → j ) es la probabilidad de que a partir de la permutación i pasemos a la permutación k en un paso, y pasemos a la permutación j después de otro paso posterior. La suma de todas las permutaciones intermedias k nos da, por lo tanto, la probabilidad total de pasar de i a j en 2 pasos .

Este argumento puede extenderse a poderes superiores de P. Una consecuencia especial es la siguiente:

p ^{( N )} _ii es la probabilidad de volver a la permutación i después de N pasos, suponiendo que comenzamos con la permutación i .

Ejemplo

Vamos a jugar con N = 3. Ya tenemos una numeración para las permutaciones. La matriz de transición correspondiente es la siguiente:

Multiplicar P consigo mismo da:

Otra multiplicación produce:

Cualquier elemento de la diagonal principal nos da la probabilidad deseada, que es _15/81 o _5/27 .

Discusión

Si bien este enfoque es matemáticamente sólido y se puede aplicar a cualquier valor de N , no es muy práctico en esta forma. La matriz de transición P tiene entradas N ! ², que se vuelven enormes muy rápido. Incluso para N = 10, el tamaño de la matriz ya supera las 13 billones de entradas. Por lo tanto, una implementación ingenua de este algoritmo parece ser inviable.

Sin embargo, en comparación con otras propuestas, este enfoque es muy estructurado y no requiere derivaciones complejas más allá de descubrir qué permutaciones son vecinas. Mi esperanza es que esta estructuración pueda ser explotada para encontrar un cálculo mucho más simple.

Por ejemplo, uno podría explotar el hecho de que todos los elementos diagonales de cualquier potencia de P son iguales. Suponiendo que podemos calcular fácilmente la traza de P ^N , la solución es simplemente tr ( P ^N ) / N ! La traza de P ^N es igual a la suma de las enésimas potencias de sus valores propios. Entonces, si tuviéramos un algoritmo eficiente para calcular los valores propios de P , estaríamos configurados. No he explorado esto más allá de calcular los valores propios hasta N = 5, sin embargo.

Answer 4

Es fácil observar los límites 1 / n ⁿ <= p <= 1 / n.

Aquí hay una idea incompleta de mostrar un límite superior exponencial inverso.

Está dibujando números de {1,2, .., n} 2n veces. Si alguno de ellos es único (ocurre exactamente una vez), la matriz definitivamente cambiará, ya que el elemento se ha ido y no puede regresar a su ubicación original.

La probabilidad de que un número fijo sea único es 2n * 1 / n * (1-1 / n) ^ (2n-1) = 2 * (1-1 / n) ^ (2n-1) que es asintóticamente 2 / e ² , acotado desde 0. [2n porque eliges en qué intento lo obtienes, 1 / n que lo obtuviste en ese intento, (1-1 / n) ^ (2n-1) que no lo obtuviste otros intentos]

Si los eventos fueran independientes, tendrías la posibilidad de que todos los números no sean únicos es (2 / e ² ) ^ n, lo que significaría p <= O ((2 / e ² ) ^ n). Desafortunadamente, no son independientes. Siento que el límite se puede mostrar con análisis más sofisticados. La palabra clave es "problema de pelotas y papeleras".

Answer 5

FYI, no estoy seguro de que el límite anterior (1 / n ^ 2) tenga:

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

Código de muestreo:

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)

Answer 6

Interesante pregunta.

Creo que la respuesta es 1 / N, pero no tengo ninguna prueba. Cuando encuentre una prueba, editaré mi respuesta.

Lo que tengo hasta ahora

If m == n, You won''t change the array. The probability to get m == n is 1/N, because there are N^2 options, and only N is suitable ((i,i) for every 0 <= i <= N-1).

Thus, we get N/N^2 = 1/N.

Denote Pk the probability that after k iterations of swaps, the array of size N will remain the same.

P1 = 1/N. (As we saw below)

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.

Answer 7

No es una solución completa, pero es algo al menos.

Tome un conjunto particular de intercambios que no tienen ningún efecto. Sabemos que debe haber sido el caso que sus swaps terminaron formando un grupo de bucles de diferentes tamaños, utilizando un total de n swaps. (A los efectos de esto, un intercambio sin efecto se puede considerar un bucle de tamaño 1)

Quizás podamos

1) Desglosarlos en grupos según los tamaños de los bucles
2) Calcula la cantidad de formas de obtener cada grupo.

(El problema principal es que hay muchísimos grupos diferentes, pero no estoy seguro de cómo calcular esto si no se tienen en cuenta las diferentes agrupaciones).

Answer 8

Todos asumen que A[i] == i , que no fue declarado explícitamente. Voy a hacer esta suposición también, pero tenga en cuenta que la probabilidad depende de los contenidos. Por ejemplo, si A[i]=0 , entonces la probabilidad = 1 para todos N.

He aquí cómo hacerlo. Sea P(n,i) la probabilidad de que la matriz resultante difiera exactamente por i transposiciones de la matriz original.

Queremos saber P(n,0) . Eso es verdad:

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)

Explicación: podemos obtener la matriz original de dos maneras, ya sea haciendo una transposición "neutral" en una matriz que ya es buena o invirtiendo la única transposición "mala". Para obtener una matriz con una sola transposición "mala", podemos tomar una matriz con 0 transposiciones malas y hacer una transposición que no sea neutral.

EDITAR: -2 en lugar de -1 en P (n-1,0)

Answer 9

Una solución simplista es

p> = 1 / N ^N

Dado que una de las posibles maneras en que la matriz permanece igual es si m = n para cada iteración. Y m es igual a n con la posibilidad 1 / N

Ciertamente es más alto que eso. La pregunta es por cuánto ...

Segundo pensamiento: También se podría argumentar que si barajas aleatoriamente una matriz, cada permutación tiene la misma probabilidad. ¡Ya que hay n! permutaciones la probabilidad de obtener solo una (la que tenemos al principio) es

p = 1 / N!

que es un poco mejor que el resultado anterior.

Como se discutió, el algoritmo está sesgado. Esto significa que no todas las permutaciones tienen la misma probabilidad. Entonces 1 / N! no es del todo exacto Tienes que descubrir cómo es la distribución de las permutaciones.

Answer 10

_{Bueno, me divertí un poco con esto. Lo primero que pensé cuando leí el problema por primera vez fue la teoría de grupos (el grupo simétrico S n , en particular). El bucle for simplemente construye una permutación σ en S n al componer transposiciones (es decir, intercambios) en cada iteración. Mi matemática no es tan espectacular y estoy un poco oxidado, así que si mi notación está fuera, tengan paciencia conmigo.}

Visión de conjunto

Sea A el evento de que nuestra matriz no cambie después de la permutación. Finalmente se nos pide que encontremos la probabilidad del evento A , Pr(A) .

Mi solución intenta seguir el siguiente procedimiento:

1. Considere todas las permutaciones posibles (es decir, reordenamientos de nuestra matriz)
2. Particiona estas permutaciones en conjuntos disjuntos en función de la cantidad de transposiciones de identidades que contienen. Esto ayuda a reducir el problema solo a las permutaciones.
3. Determine la probabilidad de obtener la permutación de identidad dado que la permutación es par (y de una longitud particular).
4. Sume estas probabilidades para obtener la probabilidad general de que la matriz no se haya modificado.

1) Posibles resultados

Observe que cada iteración del ciclo for crea un intercambio (o transposición ) que resulta en una de dos cosas (pero nunca en ambas):

1. Dos elementos son intercambiados.
2. Un elemento se intercambia consigo mismo. Para nuestros propósitos, la matriz no se modifica.

Etiquetamos el segundo caso. Definamos una transposición de identidad de la siguiente manera:

Una transposición de identidad ocurre cuando un número se intercambia consigo mismo. Es decir, cuando n == m en el ciclo de arriba para.

Para cualquier ejecución del código listado, compilamos N transposiciones. Puede haber 0, 1, 2, ... , N de las transposiciones de identidad que aparecen en esta "cadena".

Por ejemplo, considere un caso 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 **

Tenga en cuenta que hay un número impar de transposiciones que no son de identidad (1) y se modifica la matriz.

2) Particionamiento basado en el número de transposiciones de identidad

Deje que K_i sea ​​el evento en el que las transposiciones de identidad aparezcan en una permutación dada. Tenga en cuenta que esto forma una partición exhaustiva de todos los resultados posibles:

• Ninguna permutación puede tener dos cantidades diferentes de transposiciones de identidad simultáneamente, y
• Todas las permutaciones posibles deben tener entre 0 y N transposiciones de identidad.

Por lo tanto, podemos aplicar la Ley de Probabilidad Total :

Ahora finalmente podemos aprovechar la partición. Tenga en cuenta que cuando el número de transposiciones que no son de identidad es impar, no hay forma de que la matriz no se modifique *. Así:

* _{De la teoría de grupos, una permutación es par o impar pero nunca ambas. Por lo tanto, una permutación impar no puede ser la permutación de identidad (ya que la permutación de identidad es par).}

3) Determinación de probabilidades

Entonces, ahora debemos determinar dos probabilidades para Ni :

El primer término

El primer término, , representa la probabilidad de obtener una permutación con i transposiciones de identidad. Esto resulta ser binomial ya que para cada iteración del bucle for:

• El resultado es independiente de los resultados anteriores, y
• La probabilidad de crear una transposición de identidad es la misma, es decir, 1/N

Por lo tanto, para N ensayos, la probabilidad de obtener i transposiciones de identidad es:

El segundo término

Si has llegado hasta aquí, hemos reducido el problema para encontrar para N - i incluso. Esto representa la probabilidad de obtener una permutación de identidad dado que i de las transposiciones son identidades. Utilizo un enfoque de conteo ingenuo para determinar el número de formas de lograr la permutación de identidad sobre el número de permutaciones posibles.

Primero considere las permutaciones (n, m) y (m, n) equivalentes. Entonces, deje que M sea ​​la cantidad de permutaciones no identitarias posibles. Usaremos esta cantidad frecuentemente

El objetivo aquí es determinar la cantidad de formas en que se pueden combinar colecciones de transposiciones para formar la permutación de identidad. Trataré de construir la solución general junto con un ejemplo de N = 4 .

Consideremos el caso N = 4 con todas las transposiciones de identidad ( es decir, i = N = 4 ). Deje X representar una transposición de identidad. Para cada X , hay N posibilidades (son: n = m = 0, 1, 2, ... , N - 1 ). Por lo tanto, hay N^i = 4^4 posibilidades para lograr la permutación de identidad. Para completar, agregamos el coeficiente binomial, C(N, i) , para considerar el orden de las transposiciones de identidad (aquí solo equivale a 1). He tratado de describir esto a continuación con el diseño físico de los elementos anteriores y el número de posibilidades a continuación:

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

Ahora sin sustituir explícitamente N = 4 e i = 4 , podemos ver el caso general. Combinando lo anterior con el denominador encontrado previamente, encontramos:

Esto es intuitivo. De hecho, cualquier otro valor que no sea 1 probablemente te alarme. Piénselo: nos da la situación en la que se dice que todas las transposiciones de N son identidades. ¿Cuál es la probabilidad de que la matriz no haya cambiado en esta situación? Claramente, 1 .

Ahora, de nuevo para N = 4 , consideremos 2 transposiciones de identidad ( es decir, i = N - 2 = 2 ). Como una convención, colocaremos las dos identidades al final (y explicaremos el pedido más adelante). Ahora sabemos que debemos elegir dos transposiciones que, cuando se componen, se convertirán en la permutación de identidad. Coloquemos cualquier elemento en la primera ubicación, llámalo t1 . Como se indicó anteriormente, hay M posibilidades suponiendo que t1 no es una identidad (no puede ser como ya hemos colocado dos).

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

El único elemento que podría ir en el segundo lugar es el inverso de t1 , que de hecho es t1 (y este es el único por singularidad de inversa). Nuevamente incluimos el coeficiente binomial: en este caso tenemos 4 ubicaciones abiertas y estamos buscando colocar 2 permutaciones de identidad. ¿De cuántas maneras podemos hacer eso? 4 elige 2.

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

Nuevamente mirando el caso general, todo esto corresponde a:

Finalmente hacemos el caso N = 4 sin transposiciones de identidad ( es decir, i = N - 4 = 0 ). Dado que hay muchas posibilidades, comienza a ser complicado y debemos tener cuidado de no contar dos veces. Comenzamos de manera similar colocando un solo elemento en el primer punto y elaborando posibles combinaciones. Tome primero lo más fácil: la misma transposición 4 veces.

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

Consideremos ahora dos elementos únicos t1 y t2 . Hay M posibilidades para t1 y solo M-1 posibilidades para t2 (ya que t2 no puede ser igual a t1 ). Si agotamos todos los arreglos, nos quedan los siguientes patrones:

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

Ahora consideremos tres elementos únicos, t1 , t2 , t3 . t1 primero t1 y luego t2 . Como de costumbre, tenemos:

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

Todavía no podemos decir cuántas posibles t2 s todavía pueden existir, y veremos por qué en un minuto.

Ahora colocamos t1 en el tercer lugar. Aviso, t1 debe ir allí ya que si fuera en el último lugar, simplemente estaríamos recreando el (3)rd arreglo anterior. ¡El doble conteo es malo! Esto deja el tercer elemento único t3 en la posición final.

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

Entonces, ¿por qué tuvimos que tomarnos un minuto para considerar el número de t2 más de cerca? Las transposiciones t1 y t2 no pueden ser permutaciones disjuntas ( es decir , deben compartir una (y solo una, ya que tampoco pueden ser iguales) de su n o m ). La razón de esto es porque si fueran disjuntos, podríamos cambiar el orden de las permutaciones. Esto significa que estaríamos contando dos veces el (1)st arreglo.

Diga t1 = (n, m) . t2 debe tener la forma (n, x) o (y, m) para algunos x e y para no ser disyunto. Tenga en cuenta que x puede no ser n o m y y muchos no ser n o m . Por lo tanto, la cantidad de permutaciones posibles que t2 podría ser en realidad es 2 * (N - 2) .

Entonces, volviendo a nuestro diseño:

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

Ahora t3 debe ser el inverso de la composición de t1 t2 t1 . Hagámoslo de forma manual:

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

Por lo tanto, t3 debe ser (m, x) . Tenga en cuenta que esto no es disjunto a t1 y no es igual a t1 o t2 por lo que no hay doble conteo para este caso.

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

Finalmente, juntando todo esto:

4) Poniéndolo todo junto

Eso es todo. Trabaja hacia atrás, sustituyendo lo que encontramos en la suma original dada en el paso 2. Calculé la respuesta al caso N = 4 continuación. ¡Coincide con el número empírico encontrado en otra respuesta muy de cerca!

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 | |_____________|_________|

Exactitud

Sería fantástico si hubiera un resultado en la teoría de grupos para aplicar aquí ... ¡y tal vez sí! Sin duda ayudaría a que todo este tedioso recuento desaparezca por completo (y acorte el problema a algo mucho más elegante). Dejé de trabajar en N = 4 . Para N > 5 , lo que se da solo da una aproximación (qué bueno, no estoy seguro). Está bastante claro por qué es eso si lo piensas: por ejemplo, dadas las transposiciones N = 8 , hay formas claras de crear la identidad con cuatro elementos únicos que no se tienen en cuenta anteriormente. El número de formas se vuelve aparentemente más difícil de contar a medida que la permutación se hace más larga (hasta donde yo sé ...).

De todos modos, definitivamente no podría hacer algo como esto dentro del alcance de una entrevista. Llegaría tan lejos como el paso del denominador si tuviera suerte. Más allá de eso, parece bastante desagradable.

Answer 11

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! :(

Answer 12

Naive implementation in C#. The idea is to create all the possible permutations of initial array and enumerate them. Then we build a matrix of possible changes of state. Multiplying matrix by itself N times we will get the matrix 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(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;
}
}
}

Answer 13

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

Muestra de salida:

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

Answer 14

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.

Answer 15

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)