Discussion :

[xeron33]

bonsoir,
J'ai besoin d'écrire un prédicat permut(L1,L2) ou L2 est une permutation de L1 : L1 et L2 sont des listes ayant les mêmes elts mais pas necessairement dans le même ordre.
exemple :
? - permut([a,b,c],L).
L=[a,b,c]
L=[a,c,b]
L=[b,c,a]...etc...

Pour ma part j'ai écris ces 2 règles :

Code :

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

1
2
3
 
permut([],[].
permut([X1|L1],[X2|L2]):-X1=X2.

mais après je n'arrive pas à aller plus loin si quelqu'un peut m'aider.
MErçi

[luckyvae]

Tout d'abord, une remarque sur ton bout de code:

Code :

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

permut([X1|L1],[X2|L2]):-X1=X2.

peut être écrit comme

Code :

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

permut([X1|L1],[X1|L2]).

Ce qui en fait un code plus lisible car on voit directement que les premiers éléments des deux listes doivent être identiques.

Ton problème, avec ce prédicat, c'est que
1: Il ne s'applique qu'au premier élément des listes. Il faut donc le rendre récursif
2: Il est trop restrictif. Le premier élément de la liste de départ ne doit pas forcément être le premier élément de la liste permutée.

Donc, ta deuxième clause doit exprimer ça. J'espère que ça te donnera des idées pour continuer ;-)

[xeron33]

Tout d'abord, une remarque sur ton bout de code:

Code :

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

permut([X1|L1],[X2|L2]):-X1=X2.

peut être écrit comme

Code :

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

permut([X1|L1],[X1|L2]).

Ce qui en fait un code plus lisible car on voit directement que les premiers éléments des deux listes doivent être identiques.

Ton problème, avec ce prédicat, c'est que
1: Il ne s'applique qu'au premier élément des listes. Il faut donc le rendre récursif
2: Il est trop restrictif. Le premier élément de la liste de départ ne doit pas forcément être le premier élément de la liste permutée.

Donc, ta deuxième clause doit exprimer ça. J'espère que ça te donnera des idées pour continuer ;-)

MErçi pour ta réponse en terme de récursivité j'ai écris ça :

Code :

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

1
2
 
permut([X|L1],[X|L2]):- permut(L1,L2).

qui permet de travailler sur les autres eléments de la liste.
J'ai récupérer un bout de code sur un cours pour aller plus loin :

Code :

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

1
2
3
4
5
 
% enlève l'élément X de L1 et met le résultat dans L2
enleve(X,[X],[]):-!.
enleve(X,[X|L1],L1):-!.
enleve(X,[Y|L1],[Y|L2]):- enleve(X,L1,L2).

puis en puisant encore dans des cours ceçi :

Code :

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

1
2
 
permut([X|L1],[Y|L2]):- enleve(X,L2,L3),permut(L1,[Y|L3]).

qui permet le 2ème element avec le 3ème.
Ma question :
peut tu m'expliquer comment fonctionne le dernier prédicat car je ne vois pas trop comment il arrive au résultat suivant :

| ?- permut([a,b,c],L).

L = [a,b,c] ? ;

L = [a,c,b] ? ;

(15 ms) no
| ?-

MErçi de ton aide
A +

[wafadouda]

je peut vous aider dans cette fonction, puisque j'ai déjà fait ca en 1994

[xeron33]

je peut vous aider dans cette fonction, puisque j'ai déjà fait ca en 1994

Merçi pour votre proposition, j'attends votre aide donc...
A +

[Trap D]

Merçi pour votre proposition, j'attends votre aide donc...
A +

Il vaut peut-être mieux trouver soi-même la solution (avec ou sans aide), c'est plus utile

[vicnet]

Bonjour,

Je trouve le code cité bien compliqué.

En français, la permutation est définie simplement en disant qu'un élément de la liste se trouve quelque part dans l'autre liste.

Pour coder, recursivement, il faut fixer une info et vérifier le reste.

En texte, on prend le 1er element, on regarde s'il est dans la liste, si oui on l'enleve et on recommence l'opération sur le reste.
On ajoute une condition de fin quand même qui est que permuter une liste de 1 élément, ca consiste à... ne rien faire.

Ca donne ca:

Code :

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

1
2
3
4
5
6
permute([X],[X]) :- !.
 
permute(L1,[X|L2]) :-
    member(X,L1),
    delete(L1,X,L3),
    permute(L3,L2).

L'écriture de la règle de vérification d'une permutation, créé aussi automatiquement l'action de trouver toutes les permutations !

permute([a,b],[b,a]) => true
? permute([a,b],L). donne toute les solutions.

a+
Vicnet

[Trap D]

euh :

?- permute([a, a, b],[a, a, b]).
false.

?- permute([a, a, b],L).
L = [a,b] ;
L = [a,b] ;
false.

[Trap D]

Je ne sais pas où tu en es.
Pour essayer de t'aider, je pense qu'il serait intéressant que tu écrives un prédicat insert(Elem, Liste, NouvelleListe) qui réussit si NouvelleListe est une liste composée des éléments de Liste et où Elem se trouve à n'importe quelle place.
Un exemple

?- insert(a, [b, c], L).
L = [a, b, c];
L = [b, a, c];
L = [b, c, a];
false

insert doit réussir lorsque deux quelconques de ses arguments sont connus.
Ensuite, réfléchis à la manière d'utiliser ce prédicat pour définir permutation.

[vicnet]

euh :

En effet, ya bien un euh ;-)

Le pb vient de 'enleve' qui supprime toutes les valeurs identiques !

Du coup, en écrivant un enlève correct, on a:

Code :

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

1
2
3
4
5
6
7
8
supprime([X|L],X,L) :- !.
supprime([X|L],Y,[X|R]) :- supprime(L,Y,R).
 
permute([X],[X]) :- !.
permute(L1,[X|L2]) :-
    member(X,L1),
    supprime(L1,X,L3),
    permute(L3,L2).

Ca marche avec les tests.

[Trap D]

Oui, ça marche mieux comme cela !
Je préfère tout de même ma version "constructive" avec insert à ta version "destructrice" de supprime.

supprime ne marche que dans un seul sens et il y a quelques problèmes

?- supprime([a, b, c, b], b ,L).
L = [a,c,b].

?- select(b, [a, b, c, b] ,L).
L = [a,c,b] ;
L = [a,b,c] ;
false.

?- supprime(b, L, [a, c] ).
false.

?- supprime(X, [a, b ,c], [a, b]).
X = [[a,b,c],a,b].

[JeitEmgie]

Code :

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

1
2
3
4
5
6
7
8
supprime([X|L],X,L) :- !.
supprime([X|L],Y,[X|R]) :- supprime(L,Y,R).
 
permute([X],[X]) :- !.
permute(L1,[X|L2]) :-
    member(X,L1),
    supprime(L1,X,L3),
    permute(L3,L2).

Ca marche avec les tests.

appeler member() me semble inutilement coûteux…

Code :

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

1
2
3
4
5
6
 
supprime(X,[X|R],R).
supprime(X,[F|R],[F|S]) :- supprime(X,R,S).
 
permute([X|Y],Z) :- permute(Y,W), supprime(X,Z,W).   
permute([],[]).

et à mon avis
vos cuts me semblent aussi un peu prématurés… et permute([],[]) doit être défini…
du moins si vous voulez un code réutilisable…

[vicnet]

supprime ne marche que dans un seul sens et il y a quelques problèmes

En fait, dans les exemples donnés, mon supprime est mal utilisé.
Je l'ai prévu pour répondre à :

Code :

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

supprime(Liste,Element,ListeSansElement).

Element est en 2ième pos.

Visiblement, vous etes plus habitué à avoir un prototype du type

Code :

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

supprime(Element,Liste,ListeSansElement).

Ou alors il faut que je renomme 'supprimeDe' ?

Ca marche mieux avec le bon ordre.

Sauf le deuxieme test (trouver la liste correspondant à une suppression) qui ne donne qu'un seul résultat.
Surement des cuts en trop comme dit JeitEmgie.

Concernant l'apect destructif/constructif, je l'ai pensé dans le mode destructif et je l'ai codé tel quel mais philosophiquement je préfère aussi l'autre sens: prolog = psychologie :-))) ?

a+
Vicnet

[Trap D]

Je n'étais pas très bien réveillé ce matin

[xeron33]

Merçi à tous pour vos contributions voiçi le code que j'ai retenu en tenant compte de vos remarques :

Code :

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

1
2
3
4
5
6
7
8
9
10
elt(X,[Y|L]):-X=Y.
elt(X,[Y|L]):-elt(X,L).

enleve(X,[X],[]):-!.
enleve(X,[X|L1],L1):-!.
enleve(X,[Y|L1],[Y|L2]):-enleve(X,L1,L2).

permut([],[]).
permut(L1,[X|L2]):-elt(X,L1),enleve(X,L1,L3),permut(L3,L2).

Ce code fonctionne.
Toutefois si quelqu'un peut m'expliquer exactement le déroulement du prédicat permut car en essayant plusieurs fois de le faire tourner je n'arrive pas au résultat (en clair pour moi le prédicat ne devrait pas tourner puisque permut(L3,L2) içi permut([2,3],[1,2,3]) devrait répondre non car on appelle permut([2,3],[1,2,3]) celui-çi ne devrait pas aboutir pas car à ce moment là elt(X,L1) est faux puisque X=1 et L1=[2,3].
Si quelqu'un peut se pencher sur le problème
Merçi

| ?- permut([1,2,3],L).

L = [1,2,3] ? ;

L = [1,3,2] ? ;

L = [2,1,3] ? ;

L = [2,3,1] ? ;

L = [3,1,2] ? ;

L = [3,2,1] ? ;

no

[Trap D]

Je ne comprends pas, car chez moi (SWI-Prolog), ça fonctionne correctement :

2 ?- permut([1,2], [1,2,3]).
false.

3 ?- permut([2,3], [1,2,3]).
false.

[xeron33]

Je ne comprends pas, car chez moi (SWI-Prolog), ça fonctionne correctement :

Merçi pour ta réponse, pour moi aussi ça fonctionne (GNU Prolog) mais ma question est que je ne comprends pas pourquoi ça fonctionne car en le faisant "tourner à la main " pour moi ça devrait pas fonctionner :
j'avais noter :

"Ce code fonctionne.
Toutefois si quelqu'un peut m'expliquer exactement le déroulement du prédicat permut car en essayant plusieurs fois de le faire tourner je n'arrive pas au résultat (en clair pour moi le prédicat ne devrait pas tourner puisque permut(L3,L2) içi permut([2,3],[1,2,3]) devrait répondre non car on appelle permut([2,3],[1,2,3]) celui-çi ne devrait pas aboutir pas car à ce moment là elt(X,L1) est faux puisque X=1 et L1=[2,3].
Si quelqu'un peut se pencher sur le problème
Merçi"
A +

[xeron33]

Merçi pour ta réponse, pour moi aussi ça fonctionne (GNU Prolog) mais ma question est que je ne comprends pas pourquoi ça fonctionne car en le faisant "tourner à la main " pour moi ça devrait pas fonctionner :
j'avais noter :

"Ce code fonctionne.
Toutefois si quelqu'un peut m'expliquer exactement le déroulement du prédicat permut car en essayant plusieurs fois de le faire tourner je n'arrive pas au résultat (en clair pour moi le prédicat ne devrait pas tourner puisque permut(L3,L2) içi permut([2,3],[1,2,3]) devrait répondre non car on appelle permut([2,3],[1,2,3]) celui-çi ne devrait pas aboutir pas car à ce moment là elt(X,L1) est faux puisque X=1 et L1=[2,3].
Si quelqu'un peut se pencher sur le problème
Merçi"
A +

Pardon j'ai été trop vite dans ma réponse; oui en effet permut([2,3],[1,2,3]) réponds no .
Pourquoi il réponds no ?
A mon humble avis c'est parce que elt(X,L1) réponds no.
C'est pour ça que je me demande comment ce prédicat peut donner toutes les réponses pour :
| ?- permut([1,2,3],L).

L = [1,2,3] ? ;

L = [1,3,2] ? ;

L = [2,1,3] ? ;

L = [2,3,1] ? ;

L = [3,1,2] ? ;

L = [3,2,1] ? ;

no

en effet içi le prédicat liste bien toutes les permutations possibles.
A +

[Trap D]

Reprends ce que tu as écrit :

Code :

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

1
2
3
4
5
permut([],[]). (regle 1)
permut(L1,[X|L2]):-  (regle 2)
    elt(X,L1),
    enleve(X,L1,L3),
    permut(L3,L2).

Lorsque tu demandes permut([1,2,3],L). que se passe-t-il ?
On applique la règle 2 :
permut([1,2,3],[X | L2]):-
elt(X, L1), --> qui réussit pour d'abord X = 1
enleve(X, L1, L3) --> qui réussit en donnant L2 = [2,3]
permut(L3, L2). --> règle 2

permut([2, 3], [X | L2]) :-
etc etc.

Tu arrives à
permut([], []). qui réussit et tu remontes ta récursion en récupérant les valeurs successives de L2 et X.

Pour avoir les différentes valeurs, il faut remonter au différents points de choix, ici c'est elt(X, [2, 3]) qui te donnes d'abord 2 puis 3, puis après on remontera à elt(X, [1, 2, 3]) qui donne 1, puyis 2, puis 3.

[xeron33]

Reprends ce que tu as écrit :

Code :

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

1
2
3
4
5
permut([],[]). (regle 1)
permut(L1,[X|L2]):-  (regle 2)
    elt(X,L1),
    enleve(X,L1,L3),
    permut(L3,L2).

Lorsque tu demandes permut([1,2,3],L). que se passe-t-il ?
On applique la règle 2 :
permut([1,2,3],[X | L2]):-
elt(X, L1), --> qui réussit pour d'abord X = 1
enleve(X, L1, L3) --> qui réussit en donnant L2 = [2,3]
permut(L3, L2). --> règle 2

permut([2, 3], [X | L2]) :-
etc etc.

Tu arrives à
permut([], []). qui réussit et tu remontes ta récursion en récupérant les valeurs successives de L2 et X.

Pour avoir les différentes valeurs, il faut remonter au différents points de choix, ici c'est elt(X, [2, 3]) qui te donnes d'abord 2 puis 3, puis après on remontera à elt(X, [1, 2, 3]) qui donne 1, puyis 2, puis 3.

Merçi pour ta réponse. Je comprends vaguement ta démonstration et j'ai encore quelques remarques :

1) quand tu dis :"enleve(X, L1, L3) --> qui réussit en donnant L2 = [2,3]" je pense que tu voulais dire "L3=[2,3]" ?
2) quand tu dis :
"permut(L3, L2). --> règle 2 " ça veut dire que tu passes directement à la règle 2 sans passer par la règle 1 ? Pourquoi ? Ou tu y passe et elle te réponds "no" et donc tu passes alors à la règle 1 ?
3) tu dis :
"Tu arrives à
permut([], [])." Si j'ai bien compris tu "vide " la liste L1 avec enlève mais comment tu arrives à permut([],[]) ?
MErçi encore à +
Je m'absente 2 semaines à mon retour je continuerai avec plaisir avec toi ce débat.