Un problema planteado por un compañero de trabajo. Hacemos un mazo con una baraja y lo desordenamos; sabiendo dónde están las cartas, ¿es posible cortar el mazo varias veces de alguna forma para reordenarla?
Los cortes "normales" consisten en separar el mazo en dos submazos y poner encima el que estaba debajo. Este tipo de cortes no cambia el orden relativo de las cartas, simplemente las rota, cambiando la que está encima, y por tanto no sirve para ordenar mazos salvo en raros casos.
Ahora bien, si se permiten cortes en los que el mazo se divida en varios submazos, ¿se puede conseguir ordenarlo?
Un ejemplo. Tenemos un mazo de 8 cartas, de la A a la H. Originalmente están en el orden BCEAFGHD, siendo la primera carta, B, la que está arriba. Podemos cortar el mazo por dos sitios, digamos (BC)(EA)(FGHD), dividiéndolo en tres bloques de cartas: BC, EA, FGHD. Primero dejaremos sobre la mesa el bloque FGHD, luego el EA, y luego el BC. Entonces recogeremos primero el primer bloque, FGHD, luego el segundo y finalmente el tercero, y tendremos las cartas del mazo en este orden: (FGHD)(EA)(BC). Ahora podría volver a cortar este mazo en tres bloques, (FGH)(DE)(ABC), y al recogerlos tendría (ABC)(DE)(FGH), que ya está ordenado.
La cuestión es si siempre podemos hacer esto, y cuántos cortes de qué tipo son necesarios.
Pensando en mazos pequeños, enseguida se encuentra un ejemplo curioso. Si tenemos un mazo de tres cartas, y sólo permitimos hacer cortes en tres bloques, no podremos ordenarlo, porque lo único que haremos será intercambiar las cartas de arriba y abajo. Es fácil ver que, si tenemos un mazo con n cartas que siempre se corta en n bloques, lo único que haremos será invertir el orden de las cartas.
Sin embargo, tenemos el siguiente teorema:
Teorema: si se permiten cortes de dos y tres bloques, siempre es posible ordenar un mazo de n cartas con 3n-3 cortes.
Demostración: supongamos que tenemos un grupo de cartas ya ordenado, D, y una carta B que queremos poner al principio o al final de D. Empezamos con un mazo ABCDE, donde alguno de los grupos A, C o E podría estar vacío. Si queremos colocar B delante de D, cortamos ABCDE en (A)(BC)(DE) para obtener DEBCA, que partimos en (DE)(B)(CA) y obtenemos CABDE, con B justo delante de D como queríamos. Si quisiéramos colocar B detrás de D, lo que podríamos hacer es partir en mazo en (AB)(CD)(E), luego partimos ECDAB en (E)(CDA)(B), y finalmente partimos BCDAE en (BC)(D)(AE) para llegar a AEDBC. Podría parecer que estos cortes usan tres bloques, pero como alguno de los grupos podría estar vacio, en realidad a veces usaremos cortes con sólo dos bloques. Por tanto, en dos o tres cortes podemos colocar cualquier carta delante o detrás de un bloque ya ordenado, de mode que en n-1 movimientos podemos ordenar el mazo, así que como mucho son necesarios 3n-3 cortes.
Por ejemplo, usando cortes de dos o tres bloques, un baraja española de 40 cartas siempre se puede reordenar en 117 cortes o menos. No es ésta una cota demasiado astuta. Es fácil ver que una baraja de 3 cartas siempre se puede reordenar en dos cortes de dos o tres bloques, y una de cuatro cartas en tres. Por cierto, si permitimos cortes de dos, tres o cuatro bloques, las barajas de cuatro cartas siempre se pueden reordenar en dos cortes.
¿Cuántos cortes de dos o tres bloques son necesarios para una baraja con n cartas en el peor caso? Me temo que es una pregunta demasiado difícil, pero se puede encontrar una cota trivial. Por ejemplo, un mazo de 40 cartas se puede cortar en dos bloques de 39 formas, y en tres bloques de comb(39,2) = 39*38/2 = 741 formas; incluso si todas las combinaciones de estos 780 movimientos diesen siempre resultados diferentes, no podríamos conseguir las 40! permutaciones diferentes usando 16 cortes, ya que
En cambio, si permitimos cortes en dos, tres, ... , cuarenta bloques, tenemos que el número total de cortes que podemos usar es
El problema de determinar los cortes óptimos para un mazo parece difícil, pero estuve pensando en este problema y en una tarde de hackeo compulsivo escribí este programa, que usa cortes de hasta n bloques y encuentra una solución con n-1 cortes o menos. En promedio consigue ordenar un mazo de 40 cartas ordenadas aleatoriamente en unos 14 cortes; AVISO, es un programa feo de narices:
La idea es la siguiente.
Definamos un tramo como una serie de cartas (posiblemente sólo una) que ya están ordenadas crecientemente. Al hacer cortes, nunca cortaremos por la mitad un tramo (no tendría sentido deshacer el trabajo ya hecho), así que los bloques (grupos de cartas por donde corto) están formados por tramos. Obviamente, si un tramo acaba en la carta x, otro tramo empieza con la x+1, a menos que la carta x sea la última del mazo. El mazo está ordenado si y sólo si contiene un único tramo.
Si el mazo no está ordenado, entonces existe un tramo que empieza por x+1 y que aparece antes que un tramo que acaba en x. Porque, si no, todos los tramos ya estarían ordenados entre sí, y por tanto todo el mazo estaría ordenado.
Vale, pues entonces cortamos por delante de x+1, por detrás de x, y en algún sitio intermedio (como x y x+1 están en tramos diferentes sé que hay al menos una separación de tramos entre ellos por donde puedo cortar). Al reordenar los bloques habremos juntado dos tramos en un solo tramo. Así que cada vez que hacemos un corte podemos reducir en uno el número de tramos. Como empezamos con como mucho n tramos, en n-1 cortes o menos llegaremos a tener un único tramo, y entonces el mazo estará ordenado.
Un ejemplo: tengo el mazo 2 8 6 7 1 3 4 5; sus tramos son [2] [8] [6 7] [1] [3 4 5]; como el tramo [6 7] empieza por 6 y el [3 4 5] acaba en 5, parto el mazo en tres bloques ([2] [8]) ([6 7]) ([1] [3 4 5]) y al reordenarlo me quedará 1 3 4 5 6 7 2 8, que ahora tiene sólo 4 tramos: [1] [3 4 5 6 7] [2] [8].
Obviamente, hay varias formas de agrupar los tramos en bloques; si ese mazo lo hubiese partido en ([2] [8]) ([6 7] [1]) ([3 4 5]), al reordenar no sólo empalmaría [3 4 5] con [6 7], sino también [1] con [2], y me quedaría con un mazo con sólo tres tramos: [3 4 5 6 7] [1 2] [8]. Y además, hay otros pares de tramos que podría haber usado para partir el mazo; [2] y [1], y [8] y [6 7], también me habrían servido porque cumplen que la primera carta del primer tramo es la siguiente (x+1) a la última carta del segundo tramo (x).
El programa es una caca escrita en una tarde, y la estrategia heurística que sigue no está demasiado pensada, pero a pesar de todo, parece que siempre consigue reordenar un mazo de 40 cartas en 17 cortes o menos - el promedio está en unos 14 cortes. He hecho un par de pruebas con mazos de 1000 cartas, y los reordena en unos 200 cortes. Parece que en una iteración con n tramos este programa consigue juntar unos log(n) tramos, así que para reordenar un mazo de n cartas necesita algo más de n/log(n) cortes. Estoy convencido de que esto se debe de poder mejorar bastante.
No hay comentarios:
Publicar un comentario