1. #1
    Futur Membre du Club
    Homme Profil pro
    Autodidacte
    Inscrit en
    décembre 2016
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Autodidacte
    Secteur : Bâtiment Travaux Publics

    Informations forums :
    Inscription : décembre 2016
    Messages : 18
    Points : 6
    Points
    6

    Par défaut Calcul de combinaisons possibles

    Bonjour à tous,

    Connaissez vous le jeu "RUZZLE" ?

    -16 lettres
    -1 Fichier dictionnaire

    En l'espace de même pas 2 minutes il calcule les combinaisons possibles pour des mots de 2 lettres,3 lettres,4 lettres....etc...
    En plus il donne les mots possibles....

    Exemples :

    Lettres : "NCSEUEAOTEIFNALR"

    Réponse : 254 mots possibles

    -FILANTES
    -RIFLATES
    -AILANTES
    -FILATES
    -ELIATES
    .....etc....

    Quelqu'un à une idée ? plusieurs posts à ce sujet mais avec 16 lettres ça bloque .....(pour mieux voir cette rapidité :http://france.pieroxy.net/blog/pages/ruzzle/fr.html )


    Merci

  2. #2
    Expert éminent
    Homme Profil pro
    Développeur Freelance
    Inscrit en
    janvier 2009
    Messages
    3 270
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Développeur Freelance

    Informations forums :
    Inscription : janvier 2009
    Messages : 3 270
    Points : 6 908
    Points
    6 908

    Par défaut

    Bonjour,
    Pour chaque mot, il faut stocker la liste des lettres utilisées classées par ordre alphabétique, et de même pour les lettres proposées.
    Ca réduit le nombre de combinaison, vu que l'ordre des lettres ne "compte" plus.

    Une deuxième optimisation consiste à mémoriser dans la boucle de recherche les combinaisons déjà recherchées. Ainsi si une lettre apparaît plusieurs fois, les combinaisons identiques ne sont cherchées qu'une seule fois.

    Tatayo.

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 507
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 507
    Points : 3 147
    Points
    3 147

    Par défaut

    Habituellement , pour les jeux de lettres, on procède ainsi :
    1. Un dictionnaire 'astucieux'
    Mot --> Clé
    FILANTES --> AEFILNST
    ELIATES --> AEEILST

    Et on va inverser ce dictionnaire :
    Clé --> Mot
    AEFILNST --> FILANTES
    AEEILST --> ELIATES

    etc
    Pour chaque mot, on le réécrit en classant les lettres dans l'ordre alphabétique. Eventuellement, plusieurs mots ont la même clé (les anagrammes).
    Il y a 15 ou 20 ans, on trouvait dans le commerce des dictionnaires papier 'dictionnaire du scrabble', qui nous donnaient pour chaque clé, la liste des vrais-mots correspondants.

    2. Ici, avec la clé de 16 lettres, on va procéder pareil
    NCSEUEAOTEIFNALR --> AACEEEFILNNORSTU aux erreurs près.
    Et ensuite à partir de cette clé , il sera très facile d'extraire toutes les sous-clé de 2 / 3 / 4 /// 16 lettres, et pour chaque sous-clé, aller chercher dans le dictionnaire si cette sous-clé donne 1 ou plusieurs mots.

    3. On doit pouvoir optimiser un petit peu en ajoutant une condition : Si dans la sous-clé envisagée, il n'y a aucune voyelle, alors inutile d'aller lire le dictionnaire pour aller chercher ce mot.
    Et on peut aussi optimiser, car il y a des lettres en doubles voire en triple ; donc même si théoriquement on a 65535 combinaisons, on peut réduire de 10 ou 20%.

    On a au pire 65 535 Hlitrecherchepremier à effectuer, plus 10 000 ou 20 000 hlitsuivant
    Chaque lecture dure quelques millionièmes de secondes. Le traitement devrait pouvoir se faire en quelques secondes. Mais comme Windev est relativement lent pour les calculs/boucles, il faut effectivement prévoir quelques minutes.

    Edit : Vu le temps que j'ai mis à taper mon message, je me doutais qu'une autre réponse se serait intercalée !
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  4. #4
    Futur Membre du Club
    Homme Profil pro
    Autodidacte
    Inscrit en
    décembre 2016
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Autodidacte
    Secteur : Bâtiment Travaux Publics

    Informations forums :
    Inscription : décembre 2016
    Messages : 18
    Points : 6
    Points
    6

    Par défaut

    Merci pour ton aide, Wouawwww ! il va me falloir traduire cela en code...et vu mon pseudo...j'espère être encore vivant pour vivre cela!!! mais vraiment merci, je n'avais pas pensé à voir les choses comme ça.

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 507
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 507
    Points : 3 147
    Points
    3 147

    Par défaut

    C'est très exactement le problème du jeu télé "Le mot le plus long", sauf que tu as 16 lettres au lieu de 10, et tu veux tous les mots au lieu d'un seul.

    Et en cherchant "algorithme jeu le mot le plus long", on trouve différentes choses.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  6. #6
    Futur Membre du Club
    Homme Profil pro
    Autodidacte
    Inscrit en
    décembre 2016
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Autodidacte
    Secteur : Bâtiment Travaux Publics

    Informations forums :
    Inscription : décembre 2016
    Messages : 18
    Points : 6
    Points
    6

    Par défaut

    Merci beaucoup, c'est vrai c'est pas mal....pour l'instant je bosse sur la solution de "tbc92" ( lol, on occupe sa retraite comme on peut !)

    Re Bonjour,

    J'ai crée une nouvelle rubrique dans mon fichier "DICO" avec les lettres classées.
    Mais j'ai pas bien compris l'astuce des sous clés...(Non! on éclate pas de rire !)

    Au plaisir de vous lire

  7. #7
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 507
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 507
    Points : 3 147
    Points
    3 147

    Par défaut

    Pour rechercher les sous clé, il va falloir du code, beaucoup de lignes de code, et pas forcément simples.

    A partir de la clé AACEEEFILNNORSTU , on peut extraire plein de sous-clés de 2 lettres : AA AC AE, AE à nouveau , AE une 3ème fois , AF AI AL AN AN à nouveau, AO AR AS AT et AU , etc etc etc, la dernièer sous clé de 2 lettres étant TU.
    Puis plein de sous-clé de 3 lettres : AAC AAE AAE à nouveau, AAF AAI AAL etc etc ... etc, pour finir avec STU.

    Pour faire ça, il y a 2 méthodes. Tu peux faire Plusieurs fonctions :
    - fonction1 : Une fonction qui cherchera toutes les sous-clés de 2 lettres,
    - fonction2 : Une fonction qui cherchera toutes les sous-clés de 3 lettres.
    etc. et donc 15 fonctions différentes.
    Toutes ces fonctions vont se ressembler. En terme de programmation , c'est la méthode la plus facile. C'est même très facile. Par contre, en terme de maintenance, c'est une galère, puisque tu as 15 fonctions quasiment identiques à maintenir.

    Tu peux aussi essayer de faire une seule fonction, la même quelle que soit la taille de la cous-clé recherchée, mais je pense que c'est BEAUCOUP plus compliqué à faire.

    PS : Tu as créé une rubrique dans le fichier dico, avec les lettres classées. Ok. As tu déclaré cette rubrique comme CLE .
    Si tu recherches tous les mots qui ont comme clé AEILNPST , il doit te renvoyer PLIANTES, PLAINTES, PLATINES ... mais en combien de temps ? Un millième de seconde ?

    PS2 : je crois qu'il y a une série de lettres qui donne une quinzaine de mots valides (une quinzaine d'anagrammes) , mais je n'arrive pas à retrouver cette série de lettres. Tu dois pouvoir la retrouver facilement.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  8. #8
    Futur Membre du Club
    Homme Profil pro
    Autodidacte
    Inscrit en
    décembre 2016
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Autodidacte
    Secteur : Bâtiment Travaux Publics

    Informations forums :
    Inscription : décembre 2016
    Messages : 18
    Points : 6
    Points
    6

    Par défaut

    Oui bien sûr la rubrique est une CLE... regarde ce lien !!! c'est impressionnant ::http://france.pieroxy.net/blog/pages/ruzzle/fr.html
    je crois que je devrais créer une nouvelle rubrique avec pour chaque mot son nombre de lettre...
    qu'en penses tu ?

  9. #9
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 507
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 507
    Points : 3 147
    Points
    3 147

    Par défaut

    Ca va effectivement très vite, mais j'ai l'impression qu'il manque plein de mots.
    Par exemple, avec AADEEIILLNPRSSTT, je m'attendais à trouver DEPLIANTES, ALINEAS, SALI, SALIE, SALIN, SALINE , ... et aucun de ces mots n'apparaît.

    En fait, je pense que le nombre de lignes affichées est limité à 60 ou 70, et qu'il arrête la recherche dès qu'il a 70 réponses... Ca divise le temps de traitment de façon considérable.

    Ceci étant l'algorithme proposé peut avoir des temps de réponse comparables, à condition de le développer dans un langage rapide (C par exemple).
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  10. #10
    Futur Membre du Club
    Homme Profil pro
    Autodidacte
    Inscrit en
    décembre 2016
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Autodidacte
    Secteur : Bâtiment Travaux Publics

    Informations forums :
    Inscription : décembre 2016
    Messages : 18
    Points : 6
    Points
    6

    Par défaut

    En fait les mots qui manquent, c'est normal. Car "Ruzzle" impose une autre règle... C'est un jeu sur tablette et ton doigt doit suivre un chemin continu pour former le mot.
    tu comprendras mieux sur ce lien https://words-solver.com/ruzzle-triche-francais/
    Je vais abandonner, c'est au dessus de mon niveau de connaissance WinDev !
    Dommage, je voulais impressionner ma petite fille...
    Merci en tout cas pour tes réponses et pour l'intérêt que tu as apporté à mon projet.

  11. #11
    Expert éminent
    Homme Profil pro
    Développeur Freelance
    Inscrit en
    janvier 2009
    Messages
    3 270
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Développeur Freelance

    Informations forums :
    Inscription : janvier 2009
    Messages : 3 270
    Points : 6 908
    Points
    6 908

    Par défaut

    Bonjour,
    Il y a peut-être une solution, en déportant le problème sur le SGBD.
    Imaginons les tables suivantes:
    mot:
    IdMot
    Mot
    Taille

    Lettre:
    IeLettre
    Lettre

    Mot_Lettre
    IdLettre
    IdMot
    Nombre

    Il faut en premier enregistrer les lettres de l'alphabet dans la table des lettres.
    Ensuite pour chaque mot ajouté, il faut mettre le lien avec ses lettres, en spécifiant le nombre d'occurrence.
    Par exemple pour le mot tarte, il y a un lien avec a,r et e (Nombre = 1) et t (nombre = 2).

    Maintenant pour chercher les solutions, une simple requête suffit:
    Code sql : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    select m1.mot
    from mot m1,sum(ml1.nombre)
    inner join mot_lettre as ml1 on ml1.idmot = mot.idmo
    inner join lettre as l on l.idlettre = ml1.idlettre
    inner join mot_lettre as ml2 on ml2.idlettre = l.idlettre
    inner join mot as m2 on m2.idmot = ml2.idmot
    where m2.mot = 'ALPHABET' and ml2.nombre >= ml1.nombre
    group by m1.mot
    having sum(ml1.nombre) = m1.taille
    Ainsi je cherche tous les mots m1 dont les lettres sont dans le mot m2, en nombre suffisant, et pour lesquels la somme des occurrences des lettres trouvées égale la taille du mot. Le deuxième test est important, sinon la requête renvoie aussi des mots pour lesquels il manque des lettres.

    Dans l'exemple, je ne trouverai pas de mot avec 2 L, ou avec un R.
    La table lettre semble à première vue inutile, mais elle permet d'avoir des id de type entier, et (j'ai souvenir d'avoir lu quelque part que) les jointures sont plus rapieds avec des colonne de type entier...
    Maintenant il ne reste plus qu'à voir les temps de réponse avec un gros dictionnaire

    Tatayo.

  12. #12
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 507
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 507
    Points : 3 147
    Points
    3 147

    Par défaut

    Effectivement, ça change nettement la règle du jeu. Du coup la piste "" remplacer FILANTES --> AEFILNST ; ELIATES --> AEEILST etc "" ne semble plus bonne.

    @tatayo,
    Non, ta solution ne marche pas : ""ton doigt doit suivre un chemin continu pour former le mot.""

    donc si par exemple la grille contient :
    ABCD
    EFGH
    I J KL
    MNOP

    Les mots CE, DE, JE, LE ou LA ne sont pas valides ; par contre MIE ou ON sont valides.

    Là, il va falloir réfléchir un peu.

    PS : le message serait plus à sa place dans la rubrique "Algorithme " : La question est indépendante du langage utilisé ; une fois qu'on a imaginé la solution, il faudra la traduire dans un langage ( Windev ou autre)
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  13. #13
    Expert éminent
    Homme Profil pro
    Développeur Freelance
    Inscrit en
    janvier 2009
    Messages
    3 270
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Développeur Freelance

    Informations forums :
    Inscription : janvier 2009
    Messages : 3 270
    Points : 6 908
    Points
    6 908

    Par défaut

    Effectivement, je n'avais pas vu la partie "chemin", et ça complique "un peu" les choses.
    Par contre il est possible de partir de la requête pour avoir une liste de mots potentiels, et ensuite pour chacun parcourir la grille pour voir si le mot est possible.
    Avec un tableau à 2 dimensions c'est faisable, il faut juste s'assurer de ne pas utiliser 2 fois une même case.
    Il suffit de chercher la première lettre du mot, pour chaque "départ" et pour chaque lettre suivante chercher dans les 4 cases adjacente si la lettre s'y trouve, et n'a pas été encore utilisée.
    Qui s'y colle ?

    Tatayo.

  14. #14
    Futur Membre du Club
    Homme Profil pro
    Autodidacte
    Inscrit en
    décembre 2016
    Messages
    18
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Autodidacte
    Secteur : Bâtiment Travaux Publics

    Informations forums :
    Inscription : décembre 2016
    Messages : 18
    Points : 6
    Points
    6

    Par défaut

    Moi, je voudrais bien....mais franchement suis pas à votre niveau !!! j'ai appris seul, j'adore faire ça....mais là je suis passablement loin derrière vous !!

    "il faut juste s'assurer de ne pas utiliser 2 fois une même case."
    Avec finevenement quand tu passes sur la lettre (bouton) ca marche

Discussions similaires

  1. Calcul de toutes les combinaisons possibles
    Par fighterof68 dans le forum Général Algorithmique
    Réponses: 18
    Dernier message: 14/01/2015, 15h27
  2. Calcul de combinaisons possibles de parametres
    Par Kalmani dans le forum Débuter
    Réponses: 15
    Dernier message: 13/12/2013, 17h14
  3. Calculer le nombre de combinaison possible.
    Par sloshy dans le forum Mathématiques
    Réponses: 2
    Dernier message: 10/09/2009, 20h36
  4. calcul du nombre de combinaison possible
    Par Gunner4902 dans le forum Débuter
    Réponses: 10
    Dernier message: 07/07/2008, 18h55
  5. Sortir d'un tableau les combinaisons possibles
    Par juelo dans le forum Général Algorithmique
    Réponses: 33
    Dernier message: 26/03/2006, 18h11

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo