Mélange de cartes

Pour des raisons qui feront peut-être l'objet d'un prochain billet de weblog, j'ai commencé à réfléchir à comment bien mélanger un paquet de cartes, de préférence de la façon la moins chiante possible.

Et ensuite tout s'est enchaîné…

L'énoncé

Il y a moult articles sur le grand 'ternet sur comment mélanger, et des résultats sur le fait que sept ou six tours suffisent, mais je n'ai pas pu me débarrasser d'un certain doute sur mon exécution.

Surtout que le but de base n'était pas juste d'ajouter un peu d'entropie dans un système déjà chaotique, mais d'initialiser un jeu de cartes trié (parce qu'il est neuf ou qu'il sort d'un jeu qui le trie).

Comme je continue de considérer mes machines comme une extension de mon corps, et que l'informatique a de l'entropie de qualité largement supérieure à ce qui est utile pour un jeu de cartes, j'ai déjà intuitivement reformulé le problème du mélange en ces termes :

Comment appliquer une permutation stockée dans un ordinateur à un tas de cartes dans mes mains, de la façon la moins chiante possible ?

Je suppose résolu le problème de la génération aléatoire d'une permutation dans le domaine informatique, pas la peine de venir me parler de Fisher-Yates, la nouveauté est vraiment son application dans le monde physique.

On notera qu'à ce stade, le problème n'est pas complètement bien défini, parce que la notion de chiantise est vague : il y a une composante temporelle, parce que je n'ai pas envie d'y passer des heures, mais il y a aussi une composante cognitive, car j'aurais peut-être moins de patience pour une technique plus rapide mais plus monotone.

Donc je vais essayer différentes techniques pour essayer de raffiner la notion de chiantise et la raccrocher à des réalités plus objectives et mesurables.

L'accès direct

L'idée la plus évidente est de reproduire les opérations sur une structure informatique. Le paquet de cartes devant moi est une liste de cartes qu'il est facile de manipuler séquentiellement. Je peux donc prendre chaque carte, et la placer dans un tableau qui représente le tas final.

Concrètement, j'ai fait un tableau rectangulaire de dix colonnes et suffisamment de lignes (j'ai expérimenté avec des jeux de 54 et de 78 cartes), et pour chaque carte de ma pile, je regarde le rang de destination et je la pose à sa place. Une fois toutes les cartes placées, je les reprends dans l'ordre du tableau.

Informatiquement, c'est une opération linéaire dans le nombre de cartes, mais le placement d'une carte dans le tableau n'est pas tout à fait en temps constant.

Et surtout, le coût linéaire en espace physique est particulièrement problématique, parce qu'on n'a pas toujours une surface de table suffisante, et s'il faut le faire par terre ou sur un lit, l'inconfort augmente la chiantise de l'opération.

Donc c'est un premier jet, qui permet de vérifier que j'arrive bien à réaliser une permutation informatique, mais je suis sûre qu'il y a mieux.

Modéliser les manipulations physiques

Je repense souvent au tri de crêpes comme exemple de l'importance de bien modéliser le monde matériel, et comment des opérations bien choisies peuvent faire tomber les résultats théoriques les plus solides (c'est un tri en temps linéaire).

Et puis en première approximation, mon paquet de cartes est une pile de crêpes brûlées : j'ai bien accès à l'opération de retourner d'un coup tout une section du paquet, en temps constant. Malheureusement, il n'y a pas de façon de trouver une carte donnée, autre que compter la section, ce qui est en temps linéaire.

Donc retour à la case départ : j'ai mon paquet de cartes dans la main, qu'est-ce qu'une opération ?

Je peux prendre une carte du dessus du paquet, et la poser au-dessus d'une une pile qui est sur la table.

Je peux même prendre plusieurs cartes du dessus du paquet, et ce n'est pas équivalent à plusieurs fois l'opération précédente, parce que le transfert en groupe ne change pas l'ordre alors que l'empilement l'inverse. Si le groupe est assez petit (genre quatre cartes), c'est pratiquement le même coût que déplacer une seule carte. J'imagine que pour les gros groupes, il faudra prévoir un coût affine en la taille du groupe.

Je pourrais aussi prendre une ou plusieurs cartes du dessous du paquet, même si c'est une manipulation un peu plus pénible. Je pourrais aussi les mettre en dessous d'une pile existante, mais c'est une manipulation encore plus pénible.

Je ne me suis pas (encore) donné la peine d'inventer une notation pour ces différentes opérations.

Le tri par inversions

Devant la constatation que déplacer plusieurs cartes d'un coup n'est pas équivalent à déplacer plusieurs fois une seule carte, je me suis dit qu'il devrait y avoir quelque chose à faire avec ça.

Si on se limite à une seule pile d'arrivée, et qu'on inverse son ordre, le résultat est équivalent à inverser l'ordre de tous les groupes que j'ai déplacés ensemble.

Et j'ai presque été surprise de trouver de la recherche active sur ce sujet, sous le mot-clé « Sorting by Reversals » et l'abréviation MIN-SBR, qui a manifestement de l'importance en bioinformatique pour faire de la phylogénie.

J'ai passé un temps fort peu raisonnable à essayer de comprendre ces algorithmes avant de me décourager, parce qu'il faut non seulement trouver une séquence d'inversions qui génère la permutation voulue, mais ensuite trouver une façon confortable de la présenter pour manipulations physiques.

Et pour couronner le tout, le nombre d'inversions a l'air linéaire en le nombre de cartes, mais la longueur des inversions n'est pas du tout prise en compte, et je soupçonne un résultat final en chiantise quadratique.

Je revisiterai peut-être le sujet un de ces jours, mais je ne suis pour l'instant pas allée plus loin que ça.

Le tri par base

À un moment dans mes manipulations à base d'inversions, je me suis dit que les tables ne sont généralement pas encombrées au point qu'il n'y ait pas la place pour deux piles de cartes. À partir de là je ne me souviens plus trop comment j'ai pensé au tri par base, peut-être simplement parce qu'avec les crêpes, c'est l'autre exemple typique qui surpasse l'habituel n log n.

Pour l'expliquer sans prérequis, disons que le paquet de cartes dans ma main n'est pas trié, et que la permutation que je veux appliquer soit le résultat du tri. Je peux alors, à quelques inversions du paquet complet près, séparer le paquet dans ma main en une pile de cartes de rang pair et une pile de carte de rang impair, puis poser la pile paire sur la pile impaire, puis recommencer avec le deuxième bit du rang, puis le troisième, etc.

Si je ne déplace les cartes qu'une par une, avec une inversion complète à la fin, chaque tour est un tri stable suivant un seul bit, et en log n tours j'ai trié mon paquet.

Et si je commence avec un paquet trié et que j'applique la permutation inverse, j'ai bien fait le mélange que je voulais, et le tout en n log n déplacements d'une seule carte (du paquet en main vers une des deux piles sur la table).

Ce système se généralise facilement à plus que deux piles sur la table, en décomposant le rang suivant ses chiffres dans une écriture en base autant que le nombre de piles.

Et à la limite, avec autant de piles qu'il y a de cartes, on retrouve ma première idée.

Le tri fusion

Je ne sais pas ce changement de modèle est utile informatiquement, mais une autre perspective peut être utile pour les explications. Elle m'a aidée à ne pas m'embrouiller avec les inversions et à analyser chaque étape pour debug mon script.

Dans chaque tour, je distribue les cartes du paquet dans ma main sur une des deux piles, avant de mettre les piles l'une sur l'autre. Si je regarde ça en remontant le temps, c'est couper le paquet en deux et sélectionner chaque carte d'une ou de l'autre moitié pour la rassembler dans un paquet final, et c'est exactement le tri fusion.

Donc je pourrais prendre la permutation voulue, lui appliquer un tri fusion en enregistrant de quelle pile vient chaque élément, et ensuite remonter le temps avec mon paquet de cartes.

C'est l'idée que j'ai appliquée pour le premier jet de scripts python dégueulasse qui m'a servi de production.

Pour être honnête, je n'ai pas les idées super-claires sur les différentes inversions et réciproques, j'ai juste essayé les possibilités en force brute jusqu'à ce que ça marche.

Un gros inconvénient de la base en tri par base, c'est que le principe du tri stable à chaque tour impose de ne déplacer les cartes qu'une par une, et j'espérais que l'intuition supplémentaire du tri fusion permettrait d'utiliser l'opération de déplacer plusieurs cartes d'un coup.

J'ai malheureusement pas pu arriver jusque-là, alors j'ai simplement nettoyé le script pour en faire une version plus simple avec un tri par base.

Conclusion

Les scripts ci-dessus m'ont bien servi pour les mélanges de 54 et 78 cartes dont j'ai eu besoin, mais je ne suis toujours pas satisfaite de la limitation aux déplacements d'une seule carte.

Et ce n'est pas qu'une question de satisfaction intellectuelle, il y a un vrai niveau de chiantise plus élevé dans le faire passer une par une quatre cartes d'une pile à une autre, je voudrais vraiment compter les quatre cartes puis les transporter en bloc.

J'utilise surtout la version à trois piles, qui permet de mélanger ou trier ces paquets en quatre tours, et ça me prend un peu plus de trois minutes plutôt confortables.

Utiliser quatre piles permet de se limiter à trois tours pour un paquet de 54 cartes, mais j'ai plus de mal à garder les yeux sur la sortie du script (il faudra que je réessaye avec des tas beaucoup plus éloignés) et le temps de retrouver des yeux où j'en suis fait perdre plus de temps que j'en gagne en économisant un tour (j'ai un chrono à 3:18, alors qu'avec trois piles j'avais 3:06).

Il faudrait cinq piles pour appliquer une permutation à un jeu de tarot en trois tours, et descendre à deux tours réclamerait huit ou neuf piles, je crois que ça commence à être un encombrement déraisonnable. À l'inverse, je n'ai pas l'impression que le gain de place en n'utilisant que deux piles justifie l'explosion du nombre de tours.

Commentaires

Pas de commentaire pour le moment.

Poster un commentaire

Nom ou pseudonyme :

Adresse e-mail (facultatif, ne sera pas publié) :

Site web (facultatif) :

Format de mise en forme : format historique Markdown restreint

Enregistrer ces informations dans un cookie

Commentaire (sera publié dans cette page, voir les conseils de mise en forme ci-dessous) :

Message personnel (ne sera pas publié) :

Mise en forme historique : pour mettre en valeur un mot ou un groupe de mot, tapez une étoile de part et d'autre, sans mettre d'espace entre l'étoile et le mot, comme ceci : *mise en valeur*. Pour insérer un lien, mettez le entre crochets, comme ceci : [http://instinctive.eu/].

Mise en forme markdown : voir le guide détaillé, en résumé c'est le Markdown traditionnel, sans HTML ni titres, mais avec les tables PHP-Markdown-Extra.

Attention : les balises HTML entrées dans les commentaires seront affichées telles quelles, et non pas interprétées.