Discussion :

[georges_jung]

Bonjour,

Je veux développer en Prolog un prédicat qui me permet d'obtenir toutes les permutations d'une liste. Par exemple :

Code :

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

1
2
3
4
5
6
7
8
 
?- permut([a,b,c],X).
X=[a,b,c]
X=[a,c,b]
X=[b,a,c]
X=[b,c,a]
X=[c,b,a]
X=[c,a,b]

Ce prédicat ne doit pas être difficile à écrire mais je ne vois pas trop comment faire (je débute en prolog). J'ai pensé dans un premier temps à :

Code :

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

1
2
3
4
5
6
7
 
/* Le prédicat enlever permet d'enlever un élément d'une liste */
enlever(x,[x|Q],Q).
enlever(x,[y|Q],[y|Q1]):-enlever(x,Q,Q1).
/* Le prédicat permut permet de faire l'opération de permutation */
permut([],[]).
permut(L,[x|Q1]):-enlever(x,L,Q),permut(Q,Q1).

Mais ca n'a vraiment pas l'air de marcher même le prédicat enlever seul ne marche pas! Au fait, j'utilise SWI Prolog.

Si quelqu'un pouvait me donner un petit coup de pouce, ca serait gentil.

Merci d'avance

[pcaboche]

Tu es vraiment très bien parti !

Si ton prédicat enlever/3 ne marche pas, c'est parce que tu as écrit x et y en minuscules (dans ce cas il s'agit d'atomes). Il faut les écrire en majuscules (dans ce cas il s'agit de variables).

Pour info, les prédicats que tu essayes d'écrire existent en SWI et s'appellent select/3 et permutation/2.
J'imagine que ton but est de réécrire ces prédicats à titre d'exercice, ce qui est une très bonne chose quand on débute. Plus tard, tu utiliseras les prédicats déjà implémentés dans SWI.

[georges_jung]

Merci beaucoup pour ta réponse

C'est très encourageant. En effet, je dois récrire ces prédicats à titre d'exercice. Je me trouve un peu bete par rapport à l'erreur que j'ai faite pour le prédicat enlever

[georges_jung]

Voila, c'est bon tout fonctionne maintenant. J'ajoute la correction au cas où cela serve à quelqu'un un jour :

Code :

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

1
2
3
4
5
6
 
enlever(X,[X|Q],Q).
enlever(X,[Y|Q],[Y|Q1]):-enlever(X,Q,Q1).
 
permut([],[]).
permut(L,[X|Q1]):-enlever(X,L,Q),permut(Q,Q1).

Une version équivalent aurait été de faire :

Code :

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

1
2
3
4
5
 
inserer(X,L,L2):-enlever(X,L2,L).
 
permut([],[]).
permut([X|L],P):-permut(L,L1), inserer(X,L1,P).

[Cyserhof]

Je me permets de relever ce topic vieux d'un an mais qui m'a bien servi
et avec mes méninges, nous sommes arrivés à ça.
J'avais besoin d'une amélioration au prédicat de permutation "classique": il fallait en plus que je puisse choisir le nombre d'éléments de la permutation.
Par exemple:

Code :

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

1
2
3
4
5
6
7
| ?- permutations(2,[A,B,C],L).
 
L = [A,B] ? ;
 
L = [A,C] ? ;
 
L = [B,C] ? ;

Pour ceux que ça intéresse, je mets le code correspondant que j'utilise:

Code :

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

1
2
3
4
5
6
7
8
permutations(0,_,[]).
permutations(N,[X|T],[X|Comb]):-
N>0,
N1 is N-1,
permutations(N1,T,Comb).
permutations(N,[_|T],Comb):-
N>0,
permutations(N,T,Comb).