Un aleatorio aleatorio es un tipo de aleatorio donde el mazo se divide en dos particiones y las particiones se vuelven a unir para crear un nuevo mazo barajado.
Las tarjetas se unen de tal manera que las tarjetas mantienen su orden relativo dentro de la partición de la que son miembros . Por ejemplo, si la carta A está antes de la carta B en el mazo y las cartas A y B están en la misma partición, la carta A debe estar antes de la carta B en el resultado final, incluso si el número de cartas entre ellas ha aumentado. Si A y B están en particiones diferentes, pueden estar en cualquier orden, independientemente de su orden inicial, en el resultado final.
Cada riffle shuffle se puede ver como una permutación del mazo de cartas original. Por ejemplo la permutación
1,2,3 -> 1,3,2
es un riffle shuffle Si divides la baraja así
1, 2 | 3
vemos que cada tarjeta 1,3,2
tiene el mismo orden relativo que todas las demás tarjetas de su partición. 2
Todavía está después 1
.
Por otro lado, la siguiente permutación no es un riffle shuffle.
1,2,3 -> 3,2,1
Podemos ver esto porque para las dos particiones (no triviales)
1, 2 | 3
1 | 2, 3
Hay un par de cartas que no mantienen su orden relativo. En la primera partición 1
y 2
cambiar su orden, mientras que en la segunda partición 2
y 3
cambiar su orden.
Sin embargo, vemos que 3, 2, 1
se puede hacer componiendo dos barajaduras,
1, 3, 2 + 2, 3, 1 = 3, 2, 1
De hecho, un hecho bastante simple para ser probado es que cualquier permutación puede hacerse combinando un cierto número de permutaciones de riffle shuffle.
Tarea
Su tarea es hacer un programa o función que tome una permutación (de tamaño N ) como entrada y genere el menor número de permutaciones de riffle shuffle (de tamaño N ) que se pueden combinar para formar la permutación de entrada. No es necesario que el riffle baraje por sí mismo cuántos hay.
Este es el código de golf, por lo que las respuestas se puntuarán en bytes con menos bytes mejor.
Puede generar 1 o 0 para una permutación de identidad.
Casos de prueba
1,3,2 -> 1
3,2,1 -> 2
3,1,2,4 -> 1
2,3,4,1 -> 1
4,3,2,1 -> 2
fuente
4,3,2,1
ser2
? Primero nos dividimos en el medio y3,1,4,2
ganamos y luego nos dividimos en el medio nuevamente y usamos la misma permutaciónRespuestas:
Python 3 , 255 bytes
Comprueba todos los riffs posibles hasta la longitud de la lista (se requiere el número máximo), por lo que es muy lento para entradas más grandes. Probablemente también se pueda jugar bastante al golf.
Pruébalo en línea!
fuente
Limpio ,
206... 185 bytesPruébalo en línea!
Genera todos los resultados posibles de los
n
tiempos de mezcla y verifica si la lista es miembro.Si bien esta es una forma terriblemente ineficiente de resolver el problema, este código es particularmente lento debido a su uso de listas de comprensión en lugar de composición, lo que limita en gran medida cualquier reducción de gráfico elemental, y da como resultado una espectacular exhibición del recolector de basura de Clean.
Sin golf:
Pruébalo en línea!
fuente