Mezcla una matriz mientras haces que cada índice tenga la misma probabilidad de estar en cualquier índice

Quiero barajar una matriz, y que cada índice tendrá la misma probabilidad de estar en cualquier otro índice (excluyéndose a sí mismo).

Tengo esta solución, solo encuentro que siempre los últimos 2 índices siempre serán intercambiados entre sí:

void Shuffle(int arr[]. size_t n) { int newIndx = 0; int i = 0; for(; i > n - 2; ++i) { newIndx = rand() % (n - 1); if (newIndx >= i) { ++newIndx; } swap(i, newIndx, arr); } } 

pero al final puede ser que algunos índices vuelvan a su primer lugar una vez más.

¿Alguna idea?

C lang.

Una permutación (orden aleatorio) donde ningún elemento está en su lugar original se denomina desorden .

Generar alteraciones aleatorias es más difícil que generar permutaciones aleatorias, se puede hacer en tiempo y espacio lineal. (La generación de una permutación aleatoria se puede hacer en tiempo lineal y espacio constante). Aquí hay dos algoritmos posibles.


La solución más sencilla de entender es una estrategia de rechazo: hacer una baraja aleatoria de Fisher-Yates, pero si la baraja intenta colocar un elemento en su lugar original, reinicie la baraja. [Nota 1]

Dado que la probabilidad de que una mezcla aleatoria sea un trastorno es aproximadamente 1 / e , el número esperado de mezclas aleatorias realizadas es aproximadamente e (es decir, 2.71828 …). Pero como los shuffles fallidos se reinician tan pronto como se encuentra el primer punto fijo, el número total de pasos de shuffle es menor que e veces el tamaño de la matriz para un análisis detallado, consulte este documento , que demuestra el número esperado de números aleatorios que necesita el algoritmo para estar alrededor ( e −1) veces el número de elementos.

Para poder realizar la comprobación y el reinicio, debe mantener una serie de índices. La pequeña función siguiente produce un trastorno de los índices de 0 a n-1 ; es necesario aplicar la permutación a la matriz original.

 /* n must be at least 2 for this to produce meaningful results */ void derange(size_t n, size_t ind[]) { for (size_t i = 0; i < n; ++i) ind[i] = i; swap(ind, 0, randint(1, n)); for (size_t i = 1; i < n; ++i) { int r = randint(i, n); swap(ind, i, r); if (ind[i] == i) i = 0; } } 

Aquí están las dos funciones utilizadas por ese código:

 void swap(int arr[], size_t i, size_t j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } /* This is not the best possible implementation */ int randint(int low, int lim) { return low + rand() % (lim - low); } 

La siguiente función se basa en el documento de 2008 "Generación de alteraciones aleatorias" de Conrado Martínez, Alois Panholzer y Helmut Prodinger, aunque uso un mecanismo diferente para rastrear los ciclos. Su algoritmo utiliza un vector de bits de tamaño N pero utiliza una estrategia de rechazo para encontrar un elemento que no haya sido marcado. Mi algoritmo utiliza un vector explícito de índices aún no operados. El vector también es de tamaño N , que todavía es espacio O (N) [Nota 2]; ya que en aplicaciones prácticas, N no será grande, la diferencia no es IMHO significativa. El beneficio es que la selección del siguiente elemento a usar se puede hacer con una sola llamada al generador de números aleatorios. Nuevamente, esto no es particularmente significativo ya que el número esperado de rechazos en el algoritmo MP&P es muy pequeño. Pero me parece más ordenado.

La base de los algoritmos (tanto MP&P como el mío) es el procedimiento recursivo para producir un trastorno. Es importante tener en cuenta que un trastorno es necesariamente la composición de un número determinado de ciclos donde cada ciclo es de tamaño mayor que 1. (Un ciclo de tamaño 1 es un punto fijo). Por lo tanto, un trastorno de tamaño N se puede construir a partir de un desorden más pequeño usando uno de dos mecanismos:

  • Produce un desajuste de los elementos N-1 que no sea el elemento N , y agrega N a algún ciclo en cualquier punto de ese ciclo. Para hacerlo, seleccione aleatoriamente cualquier elemento j en el ciclo N-1 y coloque N inmediatamente después de j en el ciclo de j . Esta alternativa cubre todas las posibilidades donde N está en un ciclo de tamaño> 3.

  • Produce un desajuste de N-2 de los elementos N-1 distintos de N , y agrega un ciclo de tamaño 2 que consiste en N y el elemento no seleccionado del desajuste más pequeño. Esta alternativa cubre todas las posibilidades donde N está en un ciclo de tamaño 2.

Si D n es el número de desajustes de tamaño n , es fácil ver en la recursión anterior que:

 D n = (n−1)(D n−1 + D n−2 ) 

El multiplicador es n−1 en ambos casos: en la primera alternativa, se refiere al número de lugares posibles que se puede agregar N , y en la segunda alternativa al número de formas posibles para seleccionar n−2 elementos del trastorno recursivo.

Por lo tanto, si tuviéramos que producir recursivamente un trastorno aleatorio de tamaño N , seleccionaríamos aleatoriamente uno de los elementos N-1 anteriores, y luego tomaríamos una decisión aleatoria booleana sobre si producir la alternativa 1 o la alternativa 2, ponderada por el número de posibles desajustes en cada caso.

Una ventaja de este algoritmo es que puede alterar un vector arbitrario; no hay necesidad de aplicar los índices permutados al vector original como con el algoritmo de rechazo.

Como nota MP&P, el algoritmo recursivo se puede realizar iterativamente con la misma facilidad. Esto es bastante claro en el caso de la alternativa 2, ya que el nuevo ciclo de 2 ciclos se puede generar antes o después de la recursión, por lo que podría hacerse primero y luego la recursión es solo un bucle. Pero eso también es válido para la alternativa 1: podemos hacer que el elemento N el sucesor en un ciclo a un elemento j seleccionado al azar incluso antes de saber en qué ciclo j habrá finalmente. Mirado de esta manera, la diferencia entre las dos alternativas se reduce a si o no el elemento j se elimina de la consideración futura o no.

Como se muestra en la recursión, la alternativa 2 debe elegirse con probabilidad (n−1)D n−2 /D n , que es la forma en que MP&P escribe su algoritmo. Utilicé la fórmula equivalente D n−2 / (D n−1 + D n−2 ) , principalmente porque mi prototipo usaba Python (por su soporte bignum incorporado).

Sin bignums, el número de desajustes y, por lo tanto, las probabilidades deben aproximarse al double , lo que creará una ligera desviación y limitará el tamaño de la matriz a aproximadamente 170 elementos. (el long double permitiría un poco más). Si eso es demasiado limitante, podría implementar el algoritmo utilizando alguna biblioteca bignum. Para facilitar la implementación, usé la función Posix drand48 para producir double s aleatorias en el rango [0.0, 1.0). Esa no es una gran función de números aleatorios, pero probablemente es adecuada para el propósito y está disponible en la mayoría de las bibliotecas C estándar.

Dado que no se intenta verificar la singularidad de los elementos en el vector a alterar, un vector con elementos repetidos puede producir un trastorno en el que uno o más de estos elementos parecen estar en el lugar original. (En realidad es un elemento diferente con el mismo valor.)

El código:

 /* Deranges the vector `arr` (of length `n`) in place, to produce * a permutation of the original vector where every element has * been moved to a new position. Returns `true` unless the derangement * failed because `n` was 1. */ bool derange(int arr[], size_t n) { if (n < 2) return n != 1; /* Compute derangement counts ("subfactorials") */ double subfact[n]; subfact[0] = 1; subfact[1] = 0; for (size_t i = 2; i < n; ++i) subfact[i] = (i - 1) * (subfact[i - 2] + subfact[i - 1]); /* The vector 'todo' is the stack of elements which have not yet * been (fully) deranged; `u` is the count of elements in the stack */ size_t todo[n]; for (size_t i = 0; i < n; ++i) todo[i] = i; size_t u = n; /* While the stack is not empty, derange the element at the * top of the stack with some element lower down in the stack */ while (u) { size_t i = todo[--u]; /* Pop the stack */ size_t j = u * drand48(); /* Get a random stack index */ swap(arr, i, todo[j]); /* i will follow j in its cycle */ /* If we're generating a 2-cycle, remove the element at j */ if (drand48() * (subfact[u - 1] + subfact[u]) < subfact[u - 1]) todo[j] = todo[--u]; } return true; } 

Notas

  1. Muchas personas se equivocan, especialmente en ocasiones sociales como la selección de "amigos secretos" (creo que a veces se le llama "el juego de Papá Noel" en otras partes del mundo). El algoritmo incorrecto es simplemente elegir un intercambio diferente si el azar shuffle produce un punto fijo, a menos que el punto fijo esté al final, en cuyo caso se reinicia el shuffle. Esto producirá un trastorno aleatorio, pero la selección está sesgada, particularmente para vectores pequeños. Ver esta respuesta para un análisis del sesgo.

  2. Incluso si no utiliza el modelo de RAM en el que todos los enteros se consideran de tamaño fijo, el espacio utilizado sigue siendo lineal en el tamaño de la entrada en bits, ya que N valores de entrada distintos deben tener al menos N log N bits. Ni este algoritmo ni MP&P intentan alterar las listas con elementos repetidos, lo cual es un problema mucho más difícil.

Su algoritmo solo es casi correcto (lo que en algoritmos significa resultados inesperados). Debido a algunos pequeños errores dispersos, no producirá los resultados esperados.

Primero, no se garantiza que rand() % N produzca una distribución uniforme, a menos que N sea un divisor del número de valores posibles. En cualquier otro caso, obtendrá un ligero sesgo. De todos modos, mi página de manual para rand describe como un mal generador de números aleatorios , por lo que deberías intentar usar random o si está disponible arc4random_uniform .

Pero evitar que un índice regrese a su lugar original es a la vez incómodo y bastante difícil de lograr. La única forma que puedo imaginar es mantener una matriz de números [0; n [e intercambíelo de la misma forma que la matriz real para poder conocer el índice original de un número.

El código podría convertirse en:

 void Shuffle(int arr[]. size_t n) { int i, newIndx; int *indexes = malloc(n * sizeof(int)); for (i=0; i 

Cuidado: el algoritmo debe ser correcto, pero el código no se ha probado y puede contener errores tipográficos ...