Bridge et informatique

Olympiades mathématiques, énigmes et défis
Galax
Membre Relatif
Messages: 119
Enregistré le: 30 Sep 2008, 00:01

Bridge et informatique

par Galax » 10 Fév 2010, 15:23

Bonjour

Voici un problème auquel je suis confronté et n'ai pas encore la réponse, toutes les idées sont donc bienvenues.

Au bridge, il y a 4 joueurs (généralement appelés Nord Est Sud et Ouest) ayant chacun 13 cartes. On s'intéresse au nombre N total de "donnes" différentes.

Pour Nord il y a A = C(52,13) "mains" possibles,
pour Est il en reste B = C(39,13),
pour Sud C = C(26,13) et Ouest se contente des 13 cartes restantes.

Il existe donc en tout N=A*B*C (= environ 5.4 10^28) donnes différentes.

Il est donc théoriquement possible d'établir une bijection entre [0,N-1] et l'ensemble des donnes possibles. Je cherche un moyen d'établir cette bijection, c'est à dire :

1) Etant donné une donne, comment "construire" le nombre de [0,N-1] qui lui correspond

2) Etant donné un nombre de [0,N-1], comment retrouver la donne correspondante.

Des idées ?



Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 10 Fév 2010, 16:11

salut,

Cqui faut voir c'est qe si tu veux une bijection, deja tas autant delements de départ que d'arrivée. Donc N a mon avis il va approcher tes 10^28. Ca risque de coincer niveau mémoire...

Sinon, comme bijection, ben tu numerotes tes parties comme tu les calcules...

PS : pour retrouver la donne c'est un peu plus chaud. Le tout c'est de calculer d'une facon astucieuse.
la vie est une fête :)

Galax
Membre Relatif
Messages: 119
Enregistré le: 30 Sep 2008, 00:01

par Galax » 10 Fév 2010, 20:11

Non, il ne s'agit pas de tout sauvegarder mais de trouver comme tu dis une methode astucieuse de calcul, qui permette de passer aisément du nombre à la donne et vice versa.
Comme Log2(N) = 95.4.. on peut donc stocker une donne sur 96 bits binaires (soit 8 octets)

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 10 Fév 2010, 21:05

Tu peux construire une bijection si quelque part tu gardes une table de tous les C(n,k) pour n<=52 et k<=13.

Tu décides de regarder la plus petite carte de la main du joueur Nord.
Pour chaque numéro de cartes i tu connais le nombre de mains dont la plus petite carte est i (et donc le nombre de donnes qui commencent comme ça)
Donc tu sais découper ton gros intervalle en 40 sous-intervalles de longueur appropriée selon le numéro de la plus petite carte du joueur Nord.
Et ainsi de suite...

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 10 Fév 2010, 21:27

Salut,
J'avais commencé à répondre... la même chose que doraki...
A la limite, pour rajouter quelque chose, tu n'est pas obligé d'avoir un tableau contenant les coeff binomiaux, tu peut aussi utiliser une procédure qui renvoie leur valeurs (plus gourmand en temps mais moins gourmand en place mémoire...)


P.S. J'ai déjà utilisé plusieurs fois de tels système de codage/décodage pour résoudre informatiquement des casse tête et ça marche trés bien...

P.S.2 : Par rapport à ce que dit Fatal-Error (qui as raison), ce qui va être un peu gonflant, c'est effectivement la taille du "code" : tu devra faire des comparaisons (< ou >) de ce code avec des coeff binomiaux ainsi que des soustractions de "nombres" sur 12 octets (=96 bits). Les langages "courants" ne permettent pas de manipuler des entiers de cette taille. Au pire, tu devra te taper trois ou quatre procédure de "manipulation de grands entiers" (il te faut le produit et la division pour calculer les coeff binomiaux...)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

scelerat
Membre Relatif
Messages: 397
Enregistré le: 03 Aoû 2005, 15:37

par scelerat » 11 Fév 2010, 10:36

Bonjour,
Je range les 52 cartes dans l'ordre, et pour chacune, elle va etre marquee N,E,S, ou O. Cela me donne donc un nombre de 52 chiffres en base 4 qui caracterise la donne. Il faut alors determiner combien de nombres representant des donnes possibles lui sont inferieurs, ce qui se fait assez facilement : on explore le nombre chiffre apres chiffre, le nombre cherche est celui qu'on avait qu'on savait deja inferieurs des les chiffres precedents, plus ceux pour lesquels les chiffres precedents sont tous egaux et le chiffre courant inferieur.
Par exemple,
0221 3 xxx..xxx
On va ajouter au nombre calcule pour 0221000..000 le nombre pour 02210xxx..xxx, celui pour 02211xxx..xxx, et celui pour 02212xxx..xxx, ce qui donnera le nombre pour 02213000..000, et ainsi de suite.
Ces nombres sont simples a calculer si on sait obtenir les coefficients combinatoires, ce sont evidemment les combinaisons de 13- , 13-, 13-, 13- chiffres 0,1,2 et 3 dans 52-i positions.

De la meme maniere, on peut retrouver a partir du nombre, chiffre par chiffre, les 52 chiffres en base 4 qui caracterisent la donne.

Galax
Membre Relatif
Messages: 119
Enregistré le: 30 Sep 2008, 00:01

par Galax » 11 Fév 2010, 11:49

Merci pour vos réponses.

Entre temps je suis tombé sur le site d'un passionné traitant le sujet :

http://www.rpbridge.net/7z68.htm , pour ceux que ça intéresse.

Les cartes sont effectivement numérotées, le premier quart des nombres représente ainsi toutes les donnes où la 1ere carte (as de pique) est en Nord, puis le 1er quart de ce quart là, toutes les donnes ou la 2e carte (roi de pique) est en Nord, et ainsi de suite.

Deux algorithmes assez simples permettent de passer du nombre à la donne et inversement.

Reste à voir effectivement si des opérations sur un nombre de 12 octets ne sont pas trop contraignantes, le type semble avoir des "routines perso" pour manipuler de tels nombres.

scelerat
Membre Relatif
Messages: 397
Enregistré le: 03 Aoû 2005, 15:37

par scelerat » 11 Fév 2010, 12:07

En effet, c'est meme encore plus simple que je ne le pensais pour calculer les nombres de possibilites restantes.
Ceci dit, la solution ou on conserve le nombre de 52 chiffres en base 4, soit 104 bits au lieu de 96, un octet de plus, ne demande pas de calculs du tout, et si ce n'est pas pour l'amour de l'enigme, au prix de l'octet moi je ne prendrais pas le risque pour une application pratique.

Galax
Membre Relatif
Messages: 119
Enregistré le: 30 Sep 2008, 00:01

par Galax » 11 Fév 2010, 12:14

Absolument, c'était plus pour la beauté du geste que pour l'économie d'espace.
Un autre site traitant le sujet différemment et comparant les 2 méthodes , avec une appli java sympa :
http://bridge.thomasoandrews.com/impossible/

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 11 Fév 2010, 12:56

Les solution proposées par ton "passioné" et la dernière proposé par scelerat ont l'énorme avantage de proposer des codages/décodages assez simple, mais elles ont l'inconvénient d'avoir des "codes" ne correspondant pas à des distributions valides :
Pour la dernière proposée par scélérat, c'est clair vu qu'un code n'est "valide" que si le nombre de carte donné à chaque joueur vaut bien 13, pour celle de ton "passionné" (qui en fait est la même), il faut bien voir que, une fois l'as de pique en Nord, le nombre de donnes ou le roi de pique est aussi en Nord n'est pas le même que le nombre de donnes ou le roi de pique est en Est (donc, si on veut une "vrai bijectivité", ce n'est pas une division par 4 qu'il faut faire).

A toi de voir si le fait d'avoir des "codes invalide" est génant vu ce que tu compte programmer (la méthode proposée par doraki, plus complexe permet d'avoir un intervalle de codes valides)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 11 Fév 2010, 14:15

Nan, leurs méthodes sont bonnes, il me semblent qu'ils font gaffe à avoir la longueur de chaque sous-intervalle correcte (ils bidouillent le nombre K au fur et à mesure du procédé pour ça).
La méthode de choix est différente de ce que j'ai proposé, mais le principe sous-jacent est le même.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21482
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 11 Fév 2010, 14:54

O.K. pour celle du "passioné" (je n'était pas allé voir son site et avait juste lu le post de Galax parlant seulement de couper en 4).
Par contre, la deuxième de scelerat "codée sur 104 bits au lieu de 96" n'est plus bijective mais donne des algo de codage/décodage... triviaux.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Galax
Membre Relatif
Messages: 119
Enregistré le: 30 Sep 2008, 00:01

par Galax » 11 Fév 2010, 14:57

D'accord avec Doraki, leurs méthodes sont forcément bonnes puisqu'il y a N nombres et N donnes possibles ...

scelerat
Membre Relatif
Messages: 397
Enregistré le: 03 Aoû 2005, 15:37

par scelerat » 11 Fév 2010, 15:46

Ben314 a écrit:Par contre, la deuxième de scelerat "codée sur 104 bits au lieu de 96" n'est plus bijective mais donne des algo de codage/décodage... triviaux.

On peut meme descendre trivialement a 102 bits en ne codant pas la derniere carte, qui va evidemment dans la seule position libre restante.
Au cas ou il resterait des machines avec des caracteres de 6 bits, comme les CDC de ma jeunesse...

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite