Matrice de caractères et regroupements
bonjour a tous,
Je sais pas si je poste au bon endroit, mi-chemin entre math et info !!
Voila, j'aimerai en partant d'une matrice (7x7) avec une lettre dans chaque case connaitre toutes les combinaisons de groupe de 2 à 12 lettres sachant que l'on peut serpenter dans toutes les directions !!
Le but de cela est de générer un arbre binaire que je traite dans un prog info mais je bloque. Trop de possibilités !!!!
Merci d'avance.
hum on a le droit de revenir plusieurs fois sur la meme case ou pas ?
les lettres sont différentes dans toutes les cases ?
Si la réponse est oui pour ces deux questions, tu as des centaines de milliards de combinaisons ^^
Et dans l'autre cas t'as quand meme énormément de combinaisons
comme le précise folky, ça dépend de choses que tu ne précises pas dans ton énoncé.
Mais avec toutes les données on peut borner facilement le nombre de combinaisons... tu as un nombre de cases possibles pour démarrer, et à chaque rang tu peux passer à un certain nombre de cases voisines.
Par exemple si tu ne te déplaces que dans les 4 directions cardinales (pas en diagonale), et que tu n'as pas le droit de revenir sur une case déjà occupée, ça veut dire que tu as à chaque étape trois possibilités de déplacement au maximum... Du coup on peut en déduire que le nombre de combinaisons est inférieur à
7*7*(4^1+4^2+4^3...+4^11), soit 274 027 796.
Pour le programme, il suffit de faire une petite fonction récursive (pas nécessairement besoin de réellement construire l'arbre, on se contente de le parcourir implicitement) dans laquelle tu conserves un tableau des cases déjà occupées, et que tu essayes à chaque fois les quelques (max 3) possibilités de déplacement.
Si ton but est de trouver l'emplacement d'un mot dans ce genre de tableau (je te soupçonne d'être en train d'essayer de tricher aux mots mélés ou au dicoplus de ton programme télé), il te suffit de le tester à chaque fois que tu entres dans un boucle et que le rang correspond au nombre de lettres du mot cherché, et surtout tu peux t'arréter dès que la suite de lettres que tu as ne correspond plus à un mot recherché. Même si le nombre de combinaisons a l'air un peu grand, à mon avis ton pc pourra le faire très rapidement.
Maintenant, je ne sais pas exactement ce que tu veux faire, ni les détails de ta matrice et des possibilités de déplacement, mais à mon avis on reste dans quelque chose de tout à fait gérable.
merci de vos réponses, surtout 'yat' pour la qualité vu le peu d'informations.Envoyé par yat
quelques précisions:
- le contenu de la matrice est inconnu au départ (aléatoire)
- on peut se déplacer en diagonale....de gauche à droite...de haut en bas et inversement
- on utilise une seule fois une même lettre
Laurent.
Aïe... si tu peux te déplacer en diagonale, ça va tout de suite faire vachement plus de combinaisons.
D'ailleurs je viens de me rendre compte que j'ai écrit une connerie dans mon post précédent : on a trois déplacement maximum à chaque étape, et moi dans mon calcul je mets des 4 partout...
Enfin, bon... c'est pas important, dans ton cas tu vas devoir mettre des 7 à la place pour maximiser... gnarf gnarf...
