En los comentarios a artículos anteriores, ocasionalmente hay reproches: ¿por qué incluso estudiar cualquier otra clasificación, si ya existe la clasificación rápida más rápida del mundo? Dicen que todo este exótico fantasioso no tiene uso y nadie lo necesita.


Percy Diaconis , que estudió la clasificación del solitario a lo largo y ancho, cree que es la forma más rápida de organizar manualmente una baraja de cartas.

Entonces, si un matemático respetado (y un mago de cartas experimentado) no miente, entonces con el valor práctico del algoritmo, todo está en orden.

Ahora cuida tus manos.

Etapa 1. Acostado en pilas

Entonces, toma los gusanos de la cubierta. Representarán una matriz de trece elementos aleatorios.



Necesitamos descomponer las cartas en varias pilas, de modo que en cada pila las cartas sean una secuencia ordenada.

En otras palabras, nuestra tarea en esta etapa es crear rápidamente varias submatrices ordenadas a partir de la matriz no ordenada existente. Además, es altamente deseable que el número de estas submatrices sea menor, lo que significa que debe esforzarse para asegurarse de que las submatrices sean más genuinas. Esto se hace de la siguiente manera.

La primera carta es el comienzo de la primera pila.



Transferimos cartas a esta pila a su vez, hasta que la próxima carta transferida sea más pequeña que la superior en la pila.

Además, cada pila es una pila: no trabajamos con toda la pila, sino solo con la carta superior que se colocó en último lugar.



Si la carta actual es más que el mínimo en la pila, entonces tienes que crear una nueva pila, la carta actual abre una nueva pila.



¡El orden de las pilas es importante! Si su número ya es más de uno, entonces colocamos la siguiente carta no en la última pila, sino en la pila más a la izquierda, en la que podemos ponerla.

Ahora, después de la dama, necesito adjuntar un nueve en alguna parte. Mecánicamente, quiero poner la carta en la segunda pila, pero en la primera pila la carta superior es más de nueve. Entonces, podemos continuar la primera pila sin violar su orden. Los siguientes tres, que siguen a los nueve, también por cierto, van a la primera pila.



Siete y seis no se pueden agregar a la primera pila (son más grandes que la carta superior), pero todavía tienen un lugar en la segunda pila.



Ace comienza una nueva pila. La bagatela restante cae en diferentes bandejas, dependiendo de qué tan lejos a la izquierda estaba la pila donde se podía insertar.



Como resultado, las cartas se colocan en varias pilas. En cada pila, las cartas son una secuencia descendente, en la parte superior está la carta más pequeña. Las pilas son pilas.

Como primero intentamos llenar las pilas que estaban a la izquierda, formamos la menor cantidad posible. Si solo camináramos a través de la matriz y extrajéramos las submatrices decrecientes, entonces el montón naturalmente se haría mucho más grande.

Etapa 2. La fila inferior

Mueva las cartas superiores disponibles un poco hacia abajo para que se coloquen en una fila separada. Si las pilas son pilas, entonces trabajaremos con la fila inferior como con una cola.



Es importante destacar que las cartas superiores disponibles en las pilas también son una secuencia ordenada. La fila inferior ya está ordenada en orden ascendente. Lo que no es sorprendente: cuando se formaban pilas de cartas, se enviaban cartas más pequeñas a la izquierda.

En el futuro, hasta el final de la clasificación, no estamos interesados ​​en todas las cartas que se presentan en la mesa. Solo se necesitan estos:

• La carta más a la izquierda (llamémosla actual) en la fila inferior de la cola.
• En stacks-stacks, trabajamos solo con las mejores cartas disponibles. En este caso, solo se necesitan las pilas que se encuentran directamente en el mapa actual y a la izquierda. Las pilas que están a la derecha en este momento no son necesarias.

En la fila inferior, clasificamos las tarjetas de izquierda a derecha de la tarjeta. El extremo izquierdo es el mínimo actual, lo devolvemos a la fila superior original. Al mismo tiempo, cada vez que regresamos a la base otra carta, es necesario poner otra en su lugar. ¿De dónde conseguirlo? De las pilas que están sobre el mapa actual y a la izquierda del mismo, entre las cartas disponibles, se selecciona un mínimo que se mueve a la posición vacante de la carta izquierda actual en la fila inferior, y desde allí a la matriz principal.

Dos en la matriz regresa inmediatamente. El lugar desocupado es tomado por el triple (lo movemos de la primera pila a la fila inferior), y desde la fila inferior el triple, como mínimo actual, abandona la matriz principal. En las dos primeras pilas, se vuelve a buscar el mínimo, este es el cuatro, que también se va a casa. Cinco se convierte en el mínimo actual, etc.



Combinando el trabajo con un orden ascendente de la cola y un orden descendente de las pilas muy rápidamente, obtenemos todos los elementos de mínimo a máximo. Algo así, en general.

Animación de este proceso.



Si traduce todo lo anterior a Python, obtendrá esto:

from functools import total_ordering from bisect import bisect_left from heapq import merge @total_ordering class Pile(list): def __lt__(self, other): return self[-1] < other[-1] def __eq__(self, other): return self[-1] == other[-1] def patience_sort(n): piles = [] # sort into piles for x in n: new_pile = Pile([x]) i = bisect_left(piles, new_pile) if i != len(piles): piles[i].append(x) else: piles.append(new_pile) # use a heap-based merge to merge piles efficiently n[:] = merge(*[reversed(pile) for pile in piles]) 

Referencias

Clasificación de paciencia ( Google-translate )

Fuente de clasificación de paciencia

Princeton CS: subsecuencia creciente más larga

Combinación de pilas de clasificación de paciencia ( Google-translate )

Resúmenes de Wiki: clasificación de pacientes

Palabra alineada ( Google-translate )

Artículos de la serie:

• Aplicación Excel AlgoLab.xlsm
• Clases de intercambio
• Clases de inserción
  • Bibliotecario Ordenar
  • Solitario Ordenar
  • Ordenar "Torre de Hanoi"
  • Joven mesa de clasificación
  • Ordenar invertido
  • Insertar comparación de clasificación
• Ordenar por selección
• Combinar clasificaciones
• Ordenar por distribución
• Clasificación híbrida

En la aplicación AlgoLab, esta clasificación ahora está activa. Al mismo tiempo, la visualización es posible en dos modos: en forma de mapas (el modo predeterminado) y simplemente en forma de números. Sin embargo, para el estilo de la carta, es necesario que la diferencia entre los elementos máximos y mínimos en la matriz sea menor que 54 (el número de cartas en el mazo, incluyendo dos comodines). Si esta condición no se cumple o el modo de tarjeta está desactivado por completo (para esto, debe escribir card = 0 en el comentario en la celda con el nombre de clasificación), entonces la visualización será en forma de números aburridos.

Los trajes se consideran en el orden de preferencia de antigüedad: picos <clubes <panderetas <corazones.


Es decir, cualquier carta de un traje de pandereta de una pandereta es más grande que cualquier carta de un palo de club, cualquier carta de un palo de corazones es más grande que cualquier carta de un palo pico, etc. Si hacemos una analogía con los números, los picos son de 0 a 9, los clubes son de 10 a 19, los diamantes son de 20 a 29, los corazones son de 30 a 39 (sí, por supuesto, dentro del palo el número de cartas no es exactamente diez, pero entiendes lo que significa) En cuanto a la antigüedad dentro del traje , será normal: de deuce a as. También puede tomar los comodines que son mayores que todas las otras tarjetas. En este caso, el comodín rojo es más pesado que el negro.

Este artículo fue escrito con el apoyo de EDISON Software, una compañía profesional de desarrollo web que recientemente rediseñó su sitio web.