Dans les commentaires des articles précédents, il y a parfois des reproches - pourquoi même étudier d'autres triages, s'il existe déjà le tri rapide le plus rapide au monde. Ils disent que tout cet exotique fantaisiste n'a aucune utilité et que personne n'a besoin.
Percy Diaconis , qui a étudié le tri solitaire de part et d'autre, estime que c'est le moyen le plus rapide d'organiser manuellement un jeu de cartes.
Donc, si un mathématicien respecté (et un magicien de cartes expérimenté) ne ment pas, alors avec la valeur pratique de l'algorithme, tout est en ordre.
Regardez maintenant vos mains.
Étape 1. Pose en piles
Alors, prenez les vers du pont. Ils représenteront un tableau de treize éléments aléatoires.
Nous devons décomposer les cartes en plusieurs piles, de sorte que dans chaque pile, les cartes soient une séquence ordonnée.
En d'autres termes, notre tâche à ce stade est de créer rapidement plusieurs sous-réseaux ordonnés à partir du tableau non trié existant. Dans le même temps, il est hautement souhaitable que le nombre de ces sous-réseaux soit plus petit, ce qui signifie que vous devez vous efforcer de vous assurer que les sous-réseaux sont plus authentiques. Cela se fait comme suit.
La première carte est le début de la première pile.
Nous transférons les cartes dans cette pile à tour de rôle, jusqu'à ce que la prochaine carte transférée soit plus petite que la première de la pile.
De plus, chaque pile est une pile - nous ne travaillons pas avec la pile entière, mais uniquement avec la carte du dessus, qui a été placée en dernier.
Si la carte actuelle est supérieure au minimum de la pile, vous devez créer une nouvelle pile, la carte actuelle ouvre une nouvelle pile.
L'ordre des piles est important! Si leur nombre est déjà supérieur à un, alors nous plaçons la carte suivante non pas dans la dernière pile, mais dans la pile la plus à gauche, dans laquelle nous pouvons la mettre.
Maintenant, après la dame, je dois attacher un neuf quelque part. Mécaniquement, je veux mettre la carte dans la deuxième pile, mais dans la première pile, la carte du haut est plus de neuf. Ainsi, nous pouvons continuer la première pile sans violer son ordre. Les trois suivants, qui suivent les neuf, d'ailleurs, vont à la première pile.
Sept et six ne peuvent pas être ajoutés à la première pile (ils sont plus grands que la carte du dessus), mais ils ont toujours une place dans la deuxième pile.
Ace commence une nouvelle pile. La bagatelle restante tombe dans différents plateaux, selon la distance à gauche de la pile où elle pourrait être insérée.
En conséquence, les cartes sont disposées en plusieurs piles. Dans chaque pile, les cartes sont une séquence descendante, en haut se trouve la plus petite carte. Les piles sont des piles.
Puisque nous avons d'abord essayé de remplir les piles qui se trouvaient à gauche, nous avons formé la plus petite quantité possible. Si nous nous contentions de faire le tour du tableau et d'en extraire les sous-réseaux décroissants, le tas deviendrait naturellement beaucoup plus grand.
Étape 2. La rangée du bas
Déplacez un peu les premières cartes disponibles de façon à ce qu'elles se trouvent sur une ligne distincte. Si les piles sont des piles, nous travaillerons avec la ligne du bas comme avec une file d'attente.
Surtout, les premières cartes disponibles dans les piles sont également une séquence ordonnée. La ligne du bas est déjà triée par ordre croissant. Ce qui n'est pas surprenant - lors de la formation de piles de cartes, des cartes plus petites ont été envoyées à gauche.
A l'avenir, jusqu'à la fin du tri, nous ne nous intéressons pas à toutes les cartes qui sont disposées sur la table. Seuls ceux-ci sont nécessaires:
- La carte la plus à gauche (appelons-la la carte actuelle) dans la ligne inférieure de la file d'attente.
- Dans les piles-piles, nous travaillons uniquement avec les meilleures cartes disponibles. Dans ce cas, seules les piles situées directement sur la carte actuelle et à gauche sont nécessaires. Les piles qui sont à droite en ce moment ne sont pas nécessaires.
Dans la rangée du bas, nous trions les cartes de gauche à droite de la carte. Le plus à gauche est le minimum actuel, nous le renvoyons à la ligne supérieure d'origine. En même temps, chaque fois que nous retournons à la base une autre carte, il faut en mettre une autre à sa place. D'où l'obtenir? Parmi les piles qui sont au-dessus de la carte actuelle et à gauche de celle-ci - parmi les cartes disponibles, un minimum est sélectionné qui se déplace vers la position vacante de la carte gauche actuelle dans la rangée du bas, et de là vers le tableau principal.
Deux dans le tableau renvoie immédiatement. La place libérée est prise par le triple (nous le déplaçons de la première pile vers la rangée du bas), et de la rangée du bas le triple, au minimum actuel, va au tableau principal. Dans les deux premiers tas, le minimum est recherché à nouveau - c'est le quatre - qui rentre également à la maison. Cinq devient le minimum actuel, etc.
En combinant le travail avec un ordre croissant de la file d'attente et un ordre décroissant des piles très rapidement, nous obtenons tous les éléments du minimum au maximum. Quelque chose comme ça, en général.
Animation de ce processus.
Si vous traduisez tout ce qui précède en Python, vous obtenez ceci:
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 = []
Les références
Tri de la patience (
Google-translate )
Source de tri de la patience
Princeton CS: sous-séquence croissante la plus longue Combinatoire de patience triant les piles (
Google-translate )
Résumés du wiki: tri des patientsWord Aligned (
Google-translate )
Articles de série:
Dans l'application AlgoLab, ce tri est désormais actif. En même temps, la visualisation est possible dans deux modes: sous forme de cartes (le mode par défaut) et simplement sous forme de nombres. Cependant, pour le style de carte, il est nécessaire que la différence entre les éléments maximum et minimum dans le tableau soit inférieure à 54 (le nombre de cartes dans le jeu, y compris deux jokers). Si cette condition n'est pas remplie ou que le mode carte est complètement désactivé (pour cela, vous devez écrire card = 0 dans le commentaire de la cellule avec le nom de tri), la visualisation sera sous la forme de chiffres ternes.
Les combinaisons sont considérées par ordre d'ancienneté de préférence:
pics <clubs <tambourins <cœurs.C'est-à-dire que
n'importe quelle carte d'une combinaison de tambourin d'un tambourin est plus grande que
n'importe quelle carte d'une combinaison de club,
n'importe quelle carte d'une combinaison de coeurs est plus grande que
n'importe quelle carte d'une combinaison de pointe, etc. Si nous faisons une analogie avec les nombres, alors les pics sont de 0 à 9, les clubs sont de 10 à 19, les diamants sont de 20 à 29, les cœurs sont de 30 à 39 (oui, bien sûr, à l'intérieur de la combinaison, le nombre de cartes n'est pas exactement dix, mais vous comprenez ce que cela signifie). Quant à l'ancienneté
au sein de la combinaison , elle sera ordinaire: du diable à l'as. Vous pouvez également prendre les jokers qui sont plus âgés que toutes les autres cartes. Dans ce cas, le joker rouge est plus lourd que le noir.
Cet article a été écrit avec le soutien d'EDISON Software, une société de développement Web professionnelle qui a récemment repensé son site Web.