bibisousnours Posté(e) le 14 février 2004 Partager Posté(e) le 14 février 2004 coucou les INpactitiens programmeurs!! Je cherche en vain un algorithme pour trouver toutes les combinaisons d'une liste. (ordre des éléments la composant). Il me faudrait simplement l'idée de l'algorithme, je seche pour l'instant. Voici les spécifications du programme : -on ne connait pas la taille de la liste -la programmation se fait en language Prologue => pas de boucle, de "if", etc... il faut faire du récursif -une combinaison ne peut sortir qu'une seule fois -on n'a pas de fonction toute faites pour trouver le nieme élément d'une liste. Donc, s'il faut faire ca, faut créer l'algorithme -on peut savoir si un élément est membre de la liste -on peut concaténer des listes J'ai trouvé pour 2 éléments (houa, Bibisousnours, mais tu es un pro dis donc! ). Pour 3, ca se complique parce qu'en récursif ca par vite en vrille. J'ai réussi sans récursif, mais ce n'est pas la bonne méthode, puisque la liste peut faire 10^6 éléments, voire plus, donc, c'est récursif à tout prix. Je ne demande pas qu'on programme à ma place, mais simplement une idée de l'algorithme qu'un "Humain" ferait pour inverser une liste de 4 éléments (déjà ca, ca pose pas mal de pb, et ca doit etre les meme pour 10^6 éléments). Attention, l'"Humain" dois bosser en récursif. Merci, parce uqe là je seche... "make the INpact-force be with you" :clinoeil: Lien vers le commentaire Partager sur d’autres sites More sharing options...
bibisousnours Posté(e) le 14 février 2004 Auteur Partager Posté(e) le 14 février 2004 Apres avoir demandé de l'aide à une tierce personne, je me dis que je n'ai peut etre pas assez précisé certaines choses : il faut pour une liste de 3 par ex, avoir : 123 132 213 231 312 321 Voilà... mais pas forcément dans cet ordre. ca peut etre : 123 321 132 312 213 231 ou tout autre chose, tant qu'il y a les 6 et pas d'autre. donc, pour 4, ca fait 24, et pour n, ca fait n! j'espere que ca va éviter de partir sur de mauvaises pistes.... Lien vers le commentaire Partager sur d’autres sites More sharing options...
NiTrOuS Posté(e) le 14 février 2004 Partager Posté(e) le 14 février 2004 Tous mes posts sont edités suite a un topic DISCRIMINATOIRE me visant personnelement et ecrit par NITRO TECK Lien vers le commentaire Partager sur d’autres sites More sharing options...
bibisousnours Posté(e) le 14 février 2004 Auteur Partager Posté(e) le 14 février 2004 je vais essayer de préciser on part d'une liste d'éléments, liste dont on ne connait pas la taille. il faut trouver tous les arrangements possibles de cette liste. Pour une liste de 2 élément (je prends des chiffres pour les éléments, mais ca peut etre des lettres, des mots, des symbole, c'est pas ca le pb) on part de : [1,2] et on doit arriver à : [1,2],[2,1] Si on part d'une liste de 3 éléments on part de [1,2,3] et on doit arriver à : [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] (l'ordre des réponses n'est pas important). Si on part d'une liste de n éléments, il faut les n! réponses différentes. Ce que je cherche, c'est une méthode récursive pour réaliser ca (pas la programmation, mais le raisonnement, une espece de speudo-language). Sachant que comme le langage de programmation est en prologue, y'a pas de "if", de "for", de "while" de "goto", etc... Une bonne méthode pour trouver un tel algorithme, c'est de décomposer ce que fait un humain face à un tel probleme. Mais attention, faut que ce soit récursif comme raisonnement! c'est plus clair comme ca? Lien vers le commentaire Partager sur d’autres sites More sharing options...
NiTrOuS Posté(e) le 14 février 2004 Partager Posté(e) le 14 février 2004 Tous mes posts sont edités suite a un topic DISCRIMINATOIRE me visant personnelement et ecrit par NITRO TECKd ecole? Lien vers le commentaire Partager sur d’autres sites More sharing options...
bibisousnours Posté(e) le 14 février 2004 Auteur Partager Posté(e) le 14 février 2004 Pour une liste de 2 élément (je prends des chiffres pour les éléments, mais ca peut etre des lettres, des mots, des symbole, c'est pas ca le pb) on part de : [1,2] et on doit arriver à :[1,2],[2,3] on doit plutot arriver a [1,2],[2,1] non ??? C est con de pas passer par des tests de conditions ... c est un exercice d ecole? vi, dsl, c'est corrigé C'est pas que "c'est con de ne pas passer par des tests de conditions", c'est que ca n'existe pas dans le language de programmation. Du prologue, c'est pas du tout comme du Basic ou du C ou tout autre language Impératif (où les fonctions s'excécutent les unes à la suite des autres). C'est un language pour l'intelligence artificielle et c'est censé etre beaucoup plus rapide à programmer et en execution. Essaye de calculer 10.000! avec un programme en C et dis moi le temps que tu mets. En prologue, c'est instantané et le programme fait 2 lignes et ce sont celles là : fact1(1,1). fact1(N,X) :- N1 is N-1,fact1(N1,Y),X is N*Y. Enfin, oui, c'est un exo de cours... à mon avis, ca doit prendre 5 lignes, grand max, mais j'y arrive pas du tout. Lien vers le commentaire Partager sur d’autres sites More sharing options...
korrigan Posté(e) le 14 février 2004 Partager Posté(e) le 14 février 2004 oula c chaud ca....mais il me semble avoir fait ca en spe math l'an dernier... mais g t tres mauvais... le raisonnement ca doit etre du style: en fait il te faut le nombre de possibilités de placement de n nombre dans une suite. et il te faut decomposer ca en ligne de prog sachant que tu connais la reponse: pour n le resultat est factorielle de n (n!) ouep chaud ton pb... Lien vers le commentaire Partager sur d’autres sites More sharing options...
bibisousnours Posté(e) le 14 février 2004 Auteur Partager Posté(e) le 14 février 2004 oula c chaud ca....mais il me semble avoir fait ca en spe math l'an dernier...mais g t tres mauvais... le raisonnement ca doit etre du style: en fait il te faut le nombre de possibilités de placement de n nombre dans une suite. et il te faut decomposer ca en ligne de prog sachant que tu connais la reponse: pour n le resultat est factorielle de n (n!) ouep chaud ton pb... oui, mais bon, c'est dans ma présentation tout ca c'est pas trop ca le pb les listes, c'est pas des tableaux, on n'a pas à savoir la taille que ca va faire avant de les creer. Limite on ne cherche meme pas à savoir combien il y a de combinaisons. On veut juste qu'elles sortent toutes. En récursif, ca doit donner un truc du genre : je prends la combinaison du début -je la mets dans ma liste de réponse -j'échange 2 termes -je vérifie que la nvelle liste trouvée n'est pas ds la liste de réponses déjà trouvée -si elle n'y est pas, alors je la mets (si elle y est le programme s'arrete. c'est pas un "if" comme on l'entend, le prog continue tant que les conditions sont vraies) -j'échange 2 termes -je vérifie qu'elle n'est pas ds la liste de solutions... etc... quand je trouve une liste que j'ai déjà trouvée, alors, j'ai tout trouvé et j'arrete de chercher. Donc, faut un algo qui trouve les combinaisons et pas 2 fois d'affilé, sinon, il stop et ca veut dire qu'il a fini... c'est pas vraiment un exo de spé où il faut trouver le nb de solutions, ca c'est évident... Lien vers le commentaire Partager sur d’autres sites More sharing options...
NiTrOuS Posté(e) le 14 février 2004 Partager Posté(e) le 14 février 2004 désolé je ne peux plus t aider car mes posts ne servent a rien et sont ridicules selon les dires d un certain NITRO TECK Lien vers le commentaire Partager sur d’autres sites More sharing options...
warzi Posté(e) le 15 février 2004 Partager Posté(e) le 15 février 2004 tu ne sais pas creer un un systeme ou tu commences avec la solution avec tous les element a la première valeur de la liste 111 ensuite tu incrementes le premier 211 et tu continues comme cela 311 puis 121,221,321,131,231,331,112,212,312,122,222,322,132,232,332,113,213,313,123,223,323,133,233,333. si tu osbserves bien, c'est le principe de base que tu utilise pour compter, mais appliquer a l'envers. tu pars d'une liste de n element [0,1,2,3,4,5,6,7,8,9], et, tu remplaces le premier element de la solution precedente par le suivant de la liste... il ne reste plus qu'a supprimer les solutions non correcte, c'est a dire contenant des doublets... Lien vers le commentaire Partager sur d’autres sites More sharing options...
bibisousnours Posté(e) le 15 février 2004 Auteur Partager Posté(e) le 15 février 2004 désolé je ne peux plus t aider car mes posts ne servent a rien et sont ridicules selon les dires d un certain NITRO TECK c'est pas du tout le lieu, mais bon, je confirme que tu freepost pas mal et qu'en général c'est agassant parce que ce n'est pas forcément dans blabla que tu le fais. Autant Blabla est fait pour (et encore pas tous les topic), autant le reste n'est pas du tout là pour du Freepost. Si tu boudes, tant pis, on se passera de toi. Bibisousnours méchant??? oui, peut etre en ce moment Lien vers le commentaire Partager sur d’autres sites More sharing options...
bibisousnours Posté(e) le 15 février 2004 Auteur Partager Posté(e) le 15 février 2004 tu ne sais pas creer un un systeme ou tu commences avec la solution avec tous les element a la première valeur de la liste111 ensuite tu incrementes le premier 211 et tu continues comme cela 311 puis 121,221,321,131,231,331,112,212,312,122,222,322,132,232,332,113,213,313,123,223,323,133,233,333. si tu osbserves bien, c'est le principe de base que tu utilise pour compter, mais appliquer a l'envers. tu pars d'une liste de n element [0,1,2,3,4,5,6,7,8,9], et, tu remplaces le premier element de la solution precedente par le suivant de la liste... il ne reste plus qu'a supprimer les solutions non correcte, c'est a dire contenant des doublets... c'est une tres bonne idée dit donc..... .. seulement, ce n'est pas si simple. (n'empeche que sur ce coup là, j'y aurai pas pensé à cette soluce, ca vaut le coup de la retenir : Le pb, c'est que ce n'est pas une liste de nombre ou de chiffres. Ca peut etre n'importe quoi.. des symboles, des phrases, un mélange de tout ce que tu peux imaginer, etc... en plus, rien ne dis qu'il ne peut pas y avoir 2 fois le même symbole dans la liste de départ... :8 c'est pas gagné ce truc... Mais merci quand meme le coup de générer soit meme les soluce c'est peut etre à explorer Merci Lien vers le commentaire Partager sur d’autres sites More sharing options...
NiTrOuS Posté(e) le 15 février 2004 Partager Posté(e) le 15 février 2004 si c est des lettres ou des symboles tu incrémente le code ascii de la lettre ... mais dans le cas d une phrase ... mais c est vrai que c estchaud quand meme ps: dsl pour hier Lien vers le commentaire Partager sur d’autres sites More sharing options...
bibisousnours Posté(e) le 15 février 2004 Auteur Partager Posté(e) le 15 février 2004 si c est des lettres ou des symboles tu incrémente le code ascii de la lettre ... mais dans le cas d une phrase ...mais c est vrai que c estchaud quand meme ps: dsl pour hier np :8 Faut pas essayer de trouver d'astuce avec des code ASCII ou autre.... faut juste trouver une technique qui sort tous les arrangements, sans doublons et ce de facon récursive...d'ailleurs, je crois que ce n'est pas faisable avec qu'une seule fonction récursive. faut surement en faire une qui va traiter disons, la moitier des cas, et une seconde qui enchaine et va traiter le reste... Sinon, on aurait déjà trouvé Lien vers le commentaire Partager sur d’autres sites More sharing options...
NiTrOuS Posté(e) le 15 février 2004 Partager Posté(e) le 15 février 2004 si c est des lettres ou des symboles tu incrémente le code ascii de la lettre ... mais dans le cas d une phrase ...mais c est vrai que c estchaud quand meme ps: dsl pour hier np :8 Faut pas essayer de trouver d'astuce avec des code ASCII ou autre.... faut juste trouver une technique qui sort tous les arrangements, sans doublons et ce de facon récursive...d'ailleurs, je crois que ce n'est pas faisable avec qu'une seule fonction récursive. faut surement en faire une qui va traiter disons, la moitier des cas, et une seconde qui enchaine et va traiter le reste... Sinon, on aurait déjà trouvé C'est bon j'essaye de trouver des trucs GRRRR Avec la fonction modulo y a pas moyen ? Genre 321%10 tu obtient 1 tu fais 321/10 ==> 32 tu ajoute 1 au resultat de ton modulot ==>2 tu assemble les deux morceaux ==>322 Enfin tu vas encore dire que c est n importe quoi :( Lien vers le commentaire Partager sur d’autres sites More sharing options...
bibisousnours Posté(e) le 15 février 2004 Auteur Partager Posté(e) le 15 février 2004 non, c'est pas n'importe quoi, mais ce n'est pas ca... -on ne peut pas additionner (c'est des symboles qu'on manipule) :-( je crois bien ne pas être capable de résoudre ce pb.... tant pis, de toute façon, faut s'avoir accepter quand ca nous dépasse... et là, ca me dépasse. Ce qu'il faut chercher à faire, c'est la MEME CHOSE que ce que tu fais avec un papier et un crayon quand tu as une liste de 4 éléments. Une fois que tu as trouver cette méthode, faut la décortiquer, pour trouver l'action que l'on répette tout le temps (si tel est le cas) afin de rendre la fonction récurente. Si à un moment, on fait une action non récurente, faut l'analyser pour savoir exactement comment la programmer et essayer de rendre le TOUT récurent. Une fois que a marche pour 4, on regarde ce que ca change pour 5 (mais ca commence à faire bcp 5!) et on essaye avec la fonction récurente créée pour 4, de la rendre appliquable pour 5...etc.. jusqu'à ce que ca marche pour un nombre n inconnu... Ca c'est la méthode générale, mais je n'arrive pas à rendre tout ca récurrent. Quand ca marche pour un cas, si on ajoute un élément, ca ne marche plus...etc... en gros, je ne vois pas la récurrence pour un nombre n inconnu d'éléments :-( Lien vers le commentaire Partager sur d’autres sites More sharing options...
NiTrOuS Posté(e) le 15 février 2004 Partager Posté(e) le 15 février 2004 ha ok je vois ben heu alors moi non plus je sais pas, deja que je suis pas fort ... Lien vers le commentaire Partager sur d’autres sites More sharing options...
BlipBlop Posté(e) le 18 février 2004 Partager Posté(e) le 18 février 2004 Hello 3 elements: a23 a23 --> 2a3 --> 23a --> a32 --> 3a2 --> 32a En inversant la position du premier element et de son suivant, puis ainsi de suite (modulo 3) en travaillant toujours sur le meme element (ici le a), tu arrives a trouver toutes les arrangements possibles. 4 elements: ab34 ab34 -> ba34 -> b3a4 -> b34a -> a34b -> 3a4b -> 34ab -> 34ba -> a4b3 -> 4ab3 -> 4ba3 -> 4b3a -> ab34 A ce stade, on a la moitie des arrangements possibles (12/24) Apres, en inversant 2 elements de la liste de depart (sauf les 2 premiers...), puis en refaisant le meme raisonnement: a3b4 -> 3ab4 -> 3ba4 -> 3b4a -> ab43 -> ba43 -> b4a3 -> b43a -> a43b -> 4a3b -> 43ab -> 43ba -> a3b4 On a alors les 24 arrangements possibles 5 elements: 12345 12345 -> 21345 -> 23145 -> ... -> 52341 -> 12345 20 arrangements 13245 -> 31245 -> 32145 -> ... -> 53241 -> 13245 20 arrangements 12435 -> ... 20 arrangements 12354 -> ... 20 arrangements 52341 -> ... 20 arrangements On obtient deja 100/120 arrangements avec seulement des swaps d'elements cote-a-cote (modulo 5) J'ai pas pu aller plus loin pour l'instant, mais il se peut que les 20 derniers se trouvent en effectuant le swap initial sur des positions differentes (42315 ?) ou en inversant des positions plus eloignees... Pour l'algo servant a inverser une liste en recursif (t'en parle au debut du topic), c'est le meme principe: 1234 -> 1243 -> 1423 -> 4123 -> 4132 -> 4312 -> 4321 J'espere que ca t'aideras... Lien vers le commentaire Partager sur d’autres sites More sharing options...
warzi Posté(e) le 21 février 2004 Partager Posté(e) le 21 février 2004 magnifique ton idée de resolution (d'un point de vue logique en tous cas) Lien vers le commentaire Partager sur d’autres sites More sharing options...
warzi Posté(e) le 21 février 2004 Partager Posté(e) le 21 février 2004 euh si tu as la reponse, donnes la ^^ parce que j'ai beau reflechir, seules la methode de blipblop et la mienne pourraient être mises en oeuvre avec une plus grande facilité peut être pour celle a blip juste en trouvant la clé generale des swap (mathematique logique powaaaaaaa) ou la mienne mais qui devrait être plus longue sinon une autre source d'inspuration ... va voir ce que matlab fait Lien vers le commentaire Partager sur d’autres sites More sharing options...
Atlantis Posté(e) le 22 février 2004 Partager Posté(e) le 22 février 2004 si tu peux établir des lignes qui traduisent la chaine "1-2-3-4" en "a-b-c-d" (si c tes lettres qui doivent être testées) la méthode de marzi est la meilleure. t'es pas obligé de compter à l'envers remarque. pour la "traduction" soit tu peux recup dans des variables soit acceder au nième chiffre du nombre ou sinon va falloir le faire à la main dans la base n : tu fais un [1234]modulo n, tu récupères (respectivement le "4") et traduit, puis [("1234" - "4")/n ] modulo n, tu recup le "3", puis [("1234" - 3x6 - 4 )/n]modulo n, tu recup le "2" .... mais si tu peux essaie d'utiliser des variables en fait ça reviens à compter dans une base n .... Lien vers le commentaire Partager sur d’autres sites More sharing options...
Messages recommandés
Archivé
Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.