Discussion :

[BBouille]

Bonjour les amis,
J'ai commencé un truc mais j'ai interrompu mon programme quand j'ai vu que je ne pouvais plus ouvrir le fichier de sauvegarde des données en cours.
Voilà l'énoncé : on tire 5 lettres dans un sac de 100 lettres. Pour ceux qui ont reconnu le sac, c'est un sac de Scrabble.
Combien de groupes de 5 lettres peut-on tirer?
J'ai donc imbriqué 5 boucles de 1 à 100 en enregistrant les 5 lettres à chaque itération et en écartant les cas où les indices des boucles sont identiques.
Je sais que ce ne doit pas être 5x100 mais plutôt 100x99x98x97x96 mais comment être sûr qu'on ne loupe aucune combinaison?
Comme certaines lettres sont multiples je comptais supprimer les doublons après le premier traitement.
Mais comme je ne vois déjà pas comment faire le premier traitement je me suis arrêté là.
Quelqu'un aurait-il une idée, un moyen, un algorithme pour faire ça?
Merci à vous.

[valentin03]

Bonjour, je peux te proposer ça (c'est un Basic):
n = 100 dans ton cas
Les lettres sont dans a$ (qui est une chaine)
#w.txt,word$(a$,i);" ";word$(a$,j);" ";word$(a$,k);" ";word$(a$,m)
C'est l'affichage des caractères de la chaine a$ aux indices: i; j; k; m
Pour faire sur 5 lettres il faut ajouter une boucle (pas n qui sert déjà, disons "p").
et l'affichage de a$ à l'indice p.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
    for i=1 to n 
       for j=i+1 to n
          for k=j+1 to n
             for m=k+1 to n-1 ' si tu veux 
                #w.txt,word$(a$,i);" ";word$(a$,j);" ";word$(a$,k);" ";word$(a$,m)
             next m
          next k
       next j
    next i

[BBouille]

Il manque for l=k+1 to n et donc for m=l+1 to n non?
Mais c'est monstrueux comme boucles il me semble.
Je ne parviens déjà pas à remplir un fichier text pour i = 1.

[valentin03]

Il manque en effet le "l" entre le "K" et le "m"
mais ça n'a pas grand importance car on donne les noms qu'on veut aux variables, tant que l'algo reste cohérent.
Tu peux donc ajouter une boucle "l=1 to k + 1", Et la "m" devient: "m=1 to l + 1".

[BBouille]

Oui merci mais je ne vois toujours pas comment je pourrai atteindre des temps de calcul décents ni même comment sauvegarder les données par étapes intermédiaires.
Comme je n'ai jamais sauvegardé 9.034.502.400 enregistrements dans une base de données et comme ça n'a pas grande importance je te demanderai d'encoder ce petit programme et de le lancer.

[WhiteCrow]

Bonjour,

voilà un problème de combinatoire plutôt classique. Si tu ne désires que dénombrer l'ensemble des 5-combinaisons constructibles à partir du multi ensemble composé des lettres (on omet donc les deux jockers) du scrabble francophone c'est «relativement» simple. Le nombre total de 5-combinaisons est 117600.
Une méthode pour y arriver : les fonctions génératrices.

L'idée de base est simple, ce que tu cherches à calculer est le nombre r de partitions distinctes de l'entier 5 en 26 entiers (Na, Nb, Nc, … , Nz), i.e. r=Na+Nb+…+Nz, avec la contrainte supplémentaire que 0≤Na≤9 (le nombre de jeton A) et 0≤Nb≤2 (le nombre de jeton B) et … 0≤Nz≤1 (le nombre de jeton Z). Ensuite il faut remarquer que r est l'exposant de x⁵ de l'expansion du polynôme P=(1+x+x²+...+x⁹) × (1+x+x²) × … × (1+x).
Un logiciel de calcul symbolique donne pour P :


Les coefs de ce polynôme te donnent tous les dénombrements de tirage possible.
Si tu ajoutes les jokers, tu obtiens 141878 tirages distincts de 5 jetons, et 2954029 tirages distincts de 7 jetons.

[BBouille]

Ta formule est impressionnante (que je n'ai pas comprise d'ailleurs) mais 100x99x98x97x96 = 9.034.502.400
Donc je ne comprends pas comment tu es arrivé à un nombre si bas.
Par contre entre-temps je me suis rendu compte que ma question était ridicule.
Il n'y a que 402325 mots dans le dictionnaire actuel de Scrabble jusqu'à 15 lettres.
Et que 32230 de 7 lettres donc je vais partir de ça et là les temps de traitement devraient être plus raisonnables.

[WhiteCrow]

Ta formule est impressionnante (que je n'ai pas comprise d'ailleurs) mais 100x99x98x97x96 = 9.034.502.400
Donc je ne comprends pas comment tu es arrivé à un nombre si bas.

Le polynôme l'est sans doute, mais la méthode est relativement simple. Le «nombre» est bas car tu ne prends pas en compte la multiplicité de certains jetons.

Par contre entre-temps je me suis rendu compte que ma question était ridicule.
Il n'y a que 402325 mots dans le dictionnaire actuel de Scrabble jusqu'à 15 lettres.
Et que 32230 de 7 lettres donc je vais partir de ça et là les temps de traitement devraient être plus raisonnables.

Bah tout dépend de ce que tu comptes faire …

[BBouille]

Tu as sûrement raison mais j'ai du mal à comprendre ton résultat si bas.
Mon but est de savoir quel est le tirage avec 2 jokers (donc 7 lettres en tout) au premier coup d'une partie qui donne le plus de solutions.

[valentin03]

Par n'importe quel bout que tu le prenne, les factorielles ça craint (quand ça ne part pas en overflow).
Ce sera plus rapide en "C" qu'en "Python".
Tu n'a qu'à faire le tour du parc pendant que ça mouline, ça finira bien par s'arrêter.

[tbc92]

Ton premier résultat est faux.
100*99*98*97*96 : non

Simplifions beaucoup. On n'a pas 100 jetons, mais 6 jetons. Et on en tire 5. Les 6 jetons sont tous différents, pas de lettre en double.
Si je reprends ton idée, on aurait 6*5*4*3*2 tirages possibles, soit 720.
En réalité, il n'y a que 6 tirages possibles. On regarde la lettre qui reste dans le sac, et on en déduit les 5 autres.
Pourquoi un tel écart ?
Dans ton calcul, tu considères que tirer A puis B puis C, ou tirer A puis C puis B, ou tirer B puis A puis C ,ou ... ... ... , c'est différent.
Tu comptes chaque tirage 120 fois.

Il faut diviser ton nombre par 120.

Ensuite, il y a la problématique des lettres multiples. Il y a 9 lettres A dans un jeu de scrabble. ajoutons un petit n° sur chacun de ces 9 jetons, pour avoir A1, A2, A3...A9, et pareil pour les autres lettres multiples.
On a maintenant 100 jetons qui sont tous différents, donc le calcul 100*99*98*97*96/(5*4*3*2) reflète bien le nombre de tirages possibles.
Mais les tirages (A1 B C D E) ou (A2 B C D E) sont identiques au final. Il ne faut pas compter ça 2 fois, mais une seule.

Et ça se complique.

Tu pourrais faire une première simplification. Dans le sac de 100 jetons, je ne garde que 4 A, 4 E, etc etc, parce que je considère que les tirages avec uniquement des A ne vont pas être très 'porteurs'. On enlève ainsi une vingtaine de jetons. Voire beaucoup plus si on dit par exemple qu'on ne garde que 2 jetons maximum pour chaque lettre. Donc 2 jetons pour les 19 lettres qui sont multiples au départ, et 1 jeton pour les 7 autres. 45 jetons en tout au lieu de 100.


Ton approche de partir des 32230 mots de 7 lettres risquent d'être compliquée aussi.
Pour chaque mot de 7 lettres, il y a 7*6/2=21façons de choisir les 2 lettres qu'on remplace par des jokers , et donc 21 tirages de 5 lettres qui permettent de faire ce mot.
Ce calcul est valable si les 7 lettres du mot sont différentes. C'est moins que ça s'il y a au moins 2 lettres identiques.
En gros, tu vas avoir 400000 ou 500000 tirages de 5 lettres.
Ca va finalement , c'est très raisonnable.

Une autre approche, ce serait d'envisager tous les tirages avec 5 lettres différentes : 26*25*24*23*22/120=65780
Puis regarder tous les tirages avec une lettre en double : 19 façons de choisir la lettre en double, et 25*24*23/6=2300 façons de choisir les 3 autres lettres.
Puis regarder tous les tirages avec 2 lettres en double : 19*18/2=171 façons de choisir la lettre en double, et 24 façons de choisir l'autre lettre.
Les tirages avec une lettre en triple ... c'est à peu près sur que le tirage que tu recherches, celui qui donne le plus de mots ne sera pas dans cette configuration, tu peux faire l'impasse. Mais le nombre de tirages serait faible de toutes façons.

Tu as un peu plus de 100000 tirages à analyser, c'est très raisonnable.

Les 2 dernières approches sont donc très raisonnables en volume de données.

Python ou C.
Recenser tous les tirages de 5 lettres différentes, c'est une instruction en Python. Et c'est une instruction qui fait appel à une routine écrite en C. Donc c'est aussi rapide que du C.

[BBouille]

WhiteCrow,
Je sais que dans ma première approche il y a énormément de tirages identiques mais comme au départ je ne me rendais pas compte du nombre d'itérations je pensais supprimer ces doublons après.
Tu parles de 5 combinaisons mais il faut que ces combinaisons fassent partie d'un mot de 7 lettres existant.
Quelque soit le résultat du nombre de combinaisons encore faut-il trouver chaque lettre et là je ne vois pas comment faire.
tbc92,
Tu dis qu'on a 6 jetons mais le premier peut prendre 100 valeurs,... non?
Je voulais, avant de me rendre compte que c'est impossible (quasi), traiter tous les cas même avec doublons.
Je suis d'accord avec tes simplifications mais me connaissant je vais écarter des cas qui ne donneront sûrement pas le nombre maximum de solutions de 7 lettres mais où situer cette limite des cas à écarter ou pas?
Ton approche est claire dans ton esprit mais pas du tout dans le mien.
Pour le moment j'ai fait ceci:
Pour chaque mot de 7 lettres je recherche tous les mots ayant au moins 5 lettres en commun avec le mot en cours.
Je sauvegarde les lettres placées par ordre alphabétique dans un fichier.
Les 2 boucles de 1 à 32230 (mots) représentent quand même 1.038.772.900 itérations en ignorant les cas où les mots identiques se croisent.
Après une heure environ le 1/6ème de la première boucle a été parcouru donc là je peux patienter.
Si j'arrive au bout il suffira de trier alphabétiquement la liste obtenue et le groupement de lettres qui revient le plus souvent sera le premier au classement si je ne me suis pas trompé.

[tbc92]

Mon exemple simplifié avec 6 jetons...
Tu dis que le premier peut prendre 100 valeurs.
Non.
Je voulais illustrer avec un autre jeu (théorique, virtuel). Dans cet autre jeu, on aurait seulement 6 jetons, au lieu de 100. C'est tout. C'est la seule différence par rapport au Scrabble. Partout où il y a 100 dans tes calculs, on met 6 à la place.
J'ai un sac avec 6 jetons, j'en tire 5. Combien de tirages possibles.
En fait , l'erreur que tu fais, c'est que tu comptes les tirages 'ordonnés'. Alors que tirer A puis B ou B puis A, au scrabble, c'est pareil.

Maintenant, ton traitement avec ta boucle de 32230*32230 ... ça va t'emmener où ? Nulle part.

La boucle intéressante, c'est celle-ci :
Etape 1.
Pour chacun des 32230 mots
Réordonner les lettres dans l'ordre Alpha. (exemple TRAINES-->AEINRST , CHEVAUX -->ACEHUVX, TSARINE -->AEINRST RETINES-->EEINRST SENTIER-->EEINRST )
Je pense que tu es familier avec ça.

Etape 2.
Regrouper ensemble les mots qui ont les mêmes lettres , et compter le nombre de mots pour chaque groupe de 7 lettres.
Sauf erreur AEINRST(20 mots) ACEHUVX(1 mot) EEINRST(4 mots)
On devrait tomber à 20000 entrées environ, mais je suis sûr que tu connais ce nombre précis.

Etape 3.
A partir de chacune de ces entrées, regarder toutes les combinaisons de 5 lettres qu'on peut former, en retirant 2 lettres.
Si l'entrée est composée de 7 lettres différentes, on a 21 entrées différentes.
Par exemple, pour AEINRST, on a Liste n°1) AEINR AEINS AEINT AEIRS AEIRT AEIST AENRS AENRT AENST AERST AINRS AINRT AINST AIRST EINRS EINRT EINST EIRST ENRST INRST...et j'en ai oublié 1...peu importe.
Si l'entrée est composée de 6 lettres différentes, et donc une double, il y a moins de 21 entrées de 5 lettres :
Pour EEINRST, on a (Liste n°2) EEINR EEINS EEINT EEIRS EEIRT EEIST EENRS EENRT EENST EERST EINRS EINRT EINST EIRST ENRST INRST et c'est tout.

Pour chacune de ces tirages de 5 lettres (liste n°1) on a donc déjà 20 entrées, rien qu'avec les anagrammes de TSARINE
Pour EINRT, ou INRST ou quelques autres , on a 20 mots avec les anagrammes de TSARINE, et on aussi les anagrammes de SENTIER
On fait les additions, et on regarde quel tirage de 5 lettres a le meilleur résultat.

[BBouille]

Merci pour tes explications.
A y est je comprends mieux, je vais essayer de développer ça.
Tu dis que mes 2 boucles ne m'amèneront à rien, si j'ai quand même obtenu tous les mots dont au moins 5 lettres sont communes au mot de la première boucle.
Problème! J'ai trop d'occurrences. Donc il faut sans doute éliminer un mot traité (qui répond à la condition des 5 lettres) quelque part mais je ne sais pas encore où.

[Flodelarab]

Bonjour

Trouver un mot n'est pas suffisant. Il faut l'accrocher sur la grille. Et si tu veux faire un scrabble, le plus probable est 8 lettres ! 5 vraies, 2 blancs et 1 lettre sur la grille.

De plus, jouer ALERTER, ALTERER, RATELER, RELATER est identique. Pourquoi compter les mots qu'on peut former ?

[BBouille]

Hestie!
Ne viens pas compliquer les choses, j'ai déjà du mal avec le premier coup ce qui veut dire que la grille est vide

[Flodelarab]

Ok.

Spoiler : Voici la réponse :

La réponse est AESTI avec 517 mots que voici, après le code d'une ligne. Comprenne qui peut.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
$ awk -F '' '/^.{7}$/{delete l; delete t;t[""]++;for (i=1;i<=7;i++) l[$i]++; for (i in l) for (j=1;j<=l[i];j++) for (m in t) t[m""i]++; for (m in t) if (length(m)==5) s[m]++;} END{for (m in s) if (s[m]>s[max]) max=m; print max, s[max];}' mondico
AESTI 517

AIDATES
AGATISE
ALESAIT
ETALAIS
AIMATES
AMATIES
ETAMAIS
EPATAIS
AIRATES
ASIATES
ASTASIE
ETATISA
SAIETTA
EVASAIT
ATAXIES
EXTASIA
ETAYAIS
BECTAIS
BASTIDE
DEBATIS
DEBITAS
ABETIES
HABITES
BETISAI
ALBITES
ASTILBE
BALISTE
BESTIAL
BILATES
BLESAIT
BLETSAI
ETABLIS
STABILE
TALIBES
BATIMES
BITAMES
EMBATIS
BAPTISE
BIPATES
ABRITES
BITERAS
RBATIES
REBATIS
BASISTE
BASITES
BATISSE
BETISAS
BISATES
BITASSE
BATISTE
BATITES
BETISAT
BITATES
EBATTIS
BESTIAU
BASTIEZ
DACITES
DECATIS
EDICTAS
ECTASIE
CHATIES
CHIATES
ESCHAIT
SECHAIT
JACISTE
CISELAT
CATIMES
CITAMES
PACTISE
CARISTE
CIRATES
CITERAS
CRETAIS
CRIATES
RACISTE
RECITAS
TERCAIS
TIERCAS
ASCITES
CATISSE
CESSAIT
CITASSE
SCIATES
CATITES
CITATES
STATICE
TACITES
ACUITES
ACTIVES
CAVISTE
CAVITES
EXCISAT
EXCITAS
CASTIEZ
DEFAITS
SEDATIF
DIESAIT
EDITAIS
DELITAS
DESILAT
DETAILS
DILATES
DISTALE
ADMITES
MEDIATS
MEDITAS
DESIRAT
DETIRAS
RESIDAT
RIDATES
SIDERAT
STADIER
TIRADES
TRIADES
DESISTA
AUDITES
ETUDIAS
DATIVES
DEVISAT
VIDATES
AGITEES
ETIAGES
ETIGEAS
GAIETES
SIEGEAT
ATIEKES
ALITEES
ELIATES
LAITEES
EMIATES
TAMISEE
ATRESIE
RETAISE
AETITES
ATTISEE
ETATISE
ETETAIS
SAIETTE
SATIETE
EXTASIE
KIFATES
ELATIFS
FILATES
FILETAS
MEFAITS
ATTIFES
FUTAIES
FIXATES
TIAFFES
TIGEAIS
LISTAGE
LITAGES
GATISME
GITAMES
MITAGES
ATTIGES
AUGITES
VAGITES
GAGISTE
GITAGES
HESITAI
HALITES
HATIVES
HAVITES
ELISAIT
AMITIES
ATIMIES
ESTIMAI
EVITAIS
EXISTAI
TAISIEZ
LAKISTE
LIMATES
LITAMES
TAMILES
AILLETS
SELLAIT
TAILLES
TEILLAS
MATIMES
MIMATES
MITAMES
TAENIAS
BAISENT
BINATES
ACTINES
CASTINE
CATINES
NATICES
SCIANTE
DENTAIS
DESTINA
DIESANT
DINATES
TENDAIS
SATINEE
TANISEE
FEINTAS
FESTINA
FIENTAS
INFESTA
GATINES
GISANTE
GITANES
SINGEAT
TAGINES
TEASING
TSIGANE
HANTISE
TAJINES
KENTIAS
ALENTIS
ELISANT
ENLISAT
ENSILAT
LANISTE
LATINES
LESINAT
LIANTES
ENSIMAT
MAINTES
MATINES
MENTAIS
MINATES
SAMNITE
STAMINE
ASIENTO
ATONIES
OSAIENT
APTIENS
INAPTES
PANTIES
PATINES
PENSAIT
SEPTAIN
TAPINES
ARETINS
ARISENT
ENTRAIS
INERTAS
INSERAT
RATINES
RENTAIS
RESINAT
RETSINA
RIANTES
SATINER
SENTIRA
SERIANT
SERINAT
TANISER
TARINES
TARSIEN
TRAINES
TRANSIE
TSARINE
ISSANTE
NASTIES
SAINTES
SATINES
SENTAIS
TANISES
TISANES
ATTEINS
SENTAIT
STATINE
TAISENT
TEINTAS
TENTAIS
TITANES
SUAIENT
UNIATES
USAIENT
AVISENT
NATIVES
VANITES
VINATES
SATINEZ
TANISEZ
ANISENT
NANTIES
TANNISE
BAISOTE
ECOTAIS
IODATES
AGIOTES
ETIOLAS
ETOILAS
OISELAT
AMITOSE
ATOMISE
MAOISTE
MATOISE
TAOISME
ATOPIES
PATOISE
POETISA
AORISTE
EROTISA
OSERAIT
OTARIES
OTERAIS
TOISERA
TOREAIS
TAOISTE
CAPITES
DEPISTA
DEPITAS
EPIATES
PIFATES
PISTAGE
PATHIES
PIETAIS
ALPISTE
APLITES
PALITES
PILATES
PLASTIE
PLIATES
PATIMES
TAPIMES
TIPAMES
ETRIPAS
PARITES
PARTIES
PATRIES
PIASTRE
PIRATES
PISTERA
PRESTAI
PRETAIS
PRIATES
RIPATES
TIPERAS
EPISSAT
PATISSE
PESTAIS
TAPISSE
TIPASSE
PATITES
PESTAIT
TAPITES
TIPATES
EPUISAT
PIAUTES
PIEUTAS
ATYPIES
PAPISTE
PIPATES
ASTIQUE
QUETAIS
ASTERIE
ESTARIE
FRETAIS
REFAITS
TARIFES
EGRISAT
GITERAS
GRESAIT
TIGERAS
TIRAGES
TRIAGES
HATIERS
HERITAS
HERSAIT
RHETAIS
TRAHIES
ETIRAIS
ITERAIS
SERIAIT
SIERAIT
KARITES
ALTIERS
LISERAT
LISTERA
LITERAS
RESALIT
RITALES
EMIRATS
MAITRES
MARISTE
MERITAS
METRAIS
MIRATES
MITERAS
REMISAT
RIMATES
TAMIERS
TAMISER
TARIMES
TIRAMES
TRIAMES
RATISSE
RESISTA
RESTAIS
RETISSA
SATIRES
STARIES
STARISE
STERAIS
TARISSE
TERSAIS
TIRASSE
TISSERA
TRESSAI
TRIASSE
ARTISTE
ATTIERS
ATTIRES
ATTISER
RATITES
RESTAIT
STERAIT
TARITES
TERSAIT
TIRATES
TRAITES
TRIATES
AURISTE
RESITUA
SAUTIER
SITUERA
SUERAIT
TUERAIS
USERAIT
AVERTIS
ETRIVAS
RAVITES
REVISAT
RIVATES
RIVETAS
SERVAIT
SEVRAIT
VERSAIT
VETIRAS
VIRATES
EXTRAIS
RATIERS
RETIRAS
RETRAIS
SERRAIT
SERRATI
SERTIRA
STRIERA
TARSIER
TERRAIS
TIRERAS
TRIERAS
FESSAIT
FIESTAS
GITASSE
TISSAGE
HESITAS
SIESTAI
AJISTES
KASSITE
SKIATES
ALTISES
LESTAIS
LITASSE
SALITES
SILATES
ESTIMAS
MATISSE
METISSA
MISATES
MITASSE
TAMISES
ATTISES
SIESTAT
TESTAIS
ESTIVAS
VESSAIT
VISATES
EXISTAS
TASSIEZ
ZESTAIS
ASSISTE
ASSITES
SIESTAS
GITATES
SAGITTE
HESITAT
ALTISTE
LESTAIT
LITATES
ESTIMAT
MASTITE
MATITES
METTAIS
MITATES
AUTISTE
ESTIVAT
STATIVE
EXISTAT
TAXISTE
ATTISEZ
ZESTAIT
TESTAIT
LAITUES
LISTEAU
AMUITES
AUTISME
ETUVAIS
SUAVITE
TAISEUX
SAUTIEZ
ZIEUTAS
ESTIVAI
SIVAITE
ESTIVAL
LEVITAS
VITALES
LAXISTE
LAXITES
MIXATES
TAMISEZ

[BBouille]

Bonjour tbc92,
J'ai pu calculer les combinaisons de 5 lettres parmi 7 mais je n'arrive pas à le faire pour le cas où une lettre est en double.
Comment écarter les solutions qui ne conviennent pas car dans ta série on trouve quand même les combinaisons avec 2 lettres identiques?
Merci.

[Flodelarab]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Pour chaque lettre :
    Pour chaque quantité de cette lettre :
        faire ...

[tbc92]

Si la réponse de Flodelarab te convient, parfait.
Sinon, reprécise ta question, je n'ai pas trop envie de remonter la discussion pour retrouver toute l'histoire.