Aller au contenu

algorithme de combinaison d'une liste


bibisousnours

Messages recommandés

:yes: 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! :yes: ). 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...

:yes: "make the INpact-force be with you" :clinoeil:

Lien vers le commentaire
Partager sur d’autres sites

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.... :inpactamd:

Lien vers le commentaire
Partager sur d’autres sites

:inpactamd: 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

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é :oops:

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

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

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 :francais: 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

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

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 :incline:

Lien vers le commentaire
Partager sur d’autres sites

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...

c'est une tres bonne idée dit donc..... :incline:.. 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 :8)

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 :D

Lien vers le commentaire
Partager sur d’autres sites

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 :incline:

: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

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 :incline:

: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

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 :-( :incline:

Lien vers le commentaire
Partager sur d’autres sites

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

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 :byebye:

Lien vers le commentaire
Partager sur d’autres sites

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 :byebye:

en fait ça reviens à compter dans une base n ....

Lien vers le commentaire
Partager sur d’autres sites

Archivé

Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.

×
×
  • Créer...