Discussion :

[patrick974]

Bonjour tout le monde,
encore moi avec mes algorithme de tri ...
J'ai réussi à implémenter le tri par pivot (plus connu sous le nom de tri rapide), ainsi que le tri par fusion . Bon les codes sont un peu long, j'avoue. J'ai vu les solutions de mon professeur, elles font 8 lignes maxi .... Ca, c'est pas le problème, puisqu'on nous a expliqué que les solutions données étaient le fruit de plusieurs années de réflexion et que nous n'avions pas à proposer de telles implémentations (du coup on nous donne une solution, mais si on a pas la notre, c'est même pas la peine ...)!
Mes solutions ont été testé, et elles fonctionnent ! Il y a juste un truc qui m'ennuie un peu :
J'ai du mettre des "coupe-choix" après la plupart des "buts" (est-ce le bon mot ? jai pas mon cours de logique sous la main) ou plutot des conditions d'arret pour avoir unicité de la réponse(sinon, une infinité de fois la même réponse ... ). J'aimerai bien avoir l'unicité sans les coupe-choix. J'ai bien essayé de suivre avec le debugger intégré a swi, mais sans succès.
Voici mon code (celui de tri par pivot est moins long, pour ne pas encombrer le forum je ne met que celui là, en supposant que si je comprends pour ce code, ....) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
% Tri rapide
quicksort([],[]).
quicksort([X],[X]) :-
    !.
quicksort([X|Xs],Y) :-
    % on casse la liste en deux et on la trie
    qsplit([X|Xs],L1,L2),
    append(L1,[X],L1f),
    % on lance la recursivite sur les deux listes obtenues
    quicksort(L1f,L1s),
    quicksort(L2,L2s),
    % on concatene les deux listes triees
    append(L1s,L2s,Y).
% construction des listes avec  le premier element comme pivot
qsplit([],[],[]).
qsplit([_],[],[]).
qsplit([X1,X2|Xs],Y,Z) :-
    qsplit([X1|Xs],Ys,Z),
    X1>X2,!,
    append(Ys,[X2],Y).
qsplit([X1,X2|Xs],Y,Z) :-
    qsplit([X1|Xs],Y,Zs),
    append(Zs,[X2],Z).

Si vous voulez des commentaires ou d'autres choses, faîtes le moi savoir. Merci,
au revoir.

[Trap D]

quelques remarques à faire sur ton code:

Code :

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

1
2
3
4
5
6
7
8
9
10
% Tri rapide
quicksort([X|Xs],Y) :-
    % on casse la liste en deux et on la trie
    qsplit([X|Xs],L1,L2),
    append(L1,[X],L1f),
    % on lance la recursivite sur les deux listes obtenues
    quicksort(L1f,L1s),
    quicksort(L2,L2s),
    % on concatene les deux listes triees
    append(L1s,L2s,Y).

Tu sépare ta liste XS en L1 et L2. Pourquoi intègres tu X à L1 pour la retrier, on est sûr que Les éléments de L1 sont inférieurs ou égaux à X et les éléments de L2 sont supérieurs. La réintégration est inutile et de plus couteuse car append est très couteuse.
Tu auras exactement le même résultat en faisant

Code :

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

1
2
3
4
5
6
7
8
9
10
11
% Tri rapide
quicksort([X|Xs],Y) :-
    % on casse la liste en deux et on la trie
    qsplit([X|Xs],L1,L2),
    % on lance la recursivite sur les deux listes obtenues
    quicksort(L1,L1s),
    quicksort(L2,L2s),
    % on concatene les deux listes triees
    % on met X en tête des éléments de L2S 
    %puisqu'il est forcément inférieur
    append(L1s,[X | L2s] ,Y).

Tu gagnerais aussi plus de clarté en séparant déjà le pivot dans qsplit.

Code :

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

1
2
3
4
5
6
7
8
9
% Tri rapide
quicksort([X|Xs],Y) :-
    % on casse la liste en deux et on la trie
    qsplit(X, Xs,L1,L2),
    % on lance la recursivite sur les deux listes obtenues
    quicksort(L1,L1s),
    quicksort(L2,L2s),
    % on concatene les deux listes triees
    append(L1s,[X | L2s] ,Y).

Tu verras que ton code de qsplit sera plus simple et de plus tu n'auras plus besoin de cette clause

Code :

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

1
2
quicksort([X],[X]) :-
    !.

[patrick974]

Mais oui !
Merci pour toutes ces précieuses remarques. J'y aurai jamais pensé, et maintenant que tu le dis je me sens pas très futé de ne pas y avoir pensé (surtout pour le coup du append en fait ) !
Maintenant j'ai l'unicité de la réponse sans les coupe-choix !

En fait, si j'ai bien compris, mes problèmes d'unicité découlent tout simplement d'un code maladroit. Je devrai toujours avoir comme clause de condition d'arret XXXXsort([],[]), et pas d'autres clauses qui relève du bidoullage ...

Bon, je vais essayer de trouver la réponse pour mon tri par fusion. Je ne met la discussion en statut résolu tout de suite. J'aurai peut être encore des questions à te poser (espérons que non), alors ...

En tout cas, merci beaucoup.

[patrick974]

Bonjour,
j'ai essayer de chercher un peu pour mon tri par fusion, mais sans succès. Pourrais tu me donner une indication s'il te plait ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
% Tri fusion
mergesort([],[]).
mergesort([X],[X]) :-
    !.
mergesort([X|Xs],Y) :-
    size([X|Xs],N),
    N2 is N//2,
    msplit(N2,[X|Xs],L1,L2),
    mergesort(L1,L1s),
    mergesort(L2,L2s),
    mmerge(L1s,L2s,Y).
mmerge([],[],[]) :-
    !.
mmerge(X,[],X) :-
    !.
mmerge([X|Xs],[Y|Ys],Z) :-
    X=<Y,!,
    mmerge(Xs,[Y|Ys],Zs),
    append([X],Zs,Z).
mmerge(Xs,[Y|Ys],Z) :-
    mmerge(Xs,Ys,Zs),
    append([Y],Zs,Z).
msplit(0,[],[],[]) :-
    !.
msplit(S,[X|Xs],Y,Z) :-
    S>0,
    Sr is S-1,
    msplit(Sr,Xs,Ys,Z),
    append([X],Ys,Y).
msplit(0,[X|Xs],Y,Z) :-
    msplit(0,Xs,Y,Zs),
    append([X],Zs,Z).
size([],0).
size([_|Xs],N) :-
    size(Xs,Nn),
    N is Nn+1.

J'ai pas mi de commentaire parse que les noms de fonction parle d'eux même je trouve, mais je peux en rajouter ...
Merci, au revoir.

[Trap D]

Salut

Tu as une mauvaise vision des listes en Prolog (peut-être es-tu habitué à programmer en C ou en java).
En Prolog on a accès à une liste par l'intermédiaire de son premier élément et de son reste qui est une liste. La longueur de la liste n'est en général pas utile à connaître (sauf cas particuliers bien sûr).
Ici tu veux partager ta liste en deux, sans condition particulière, donc tu parcours ta liste 2 éléments par 2 éléments, le premier tu le mets "à gauche" et le deuxième "à droite" tout simplement.
Les conditions d'arrêt sont j'ai une liste vide à partager ou une liste à un seul élément.
split peut s'écrire :

Code :

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

1
2
3
4
split([], [], []).
split([X], [X], []).
split([X, Y | T], [X | L1], [Y | L2]):-
	split(T, L1, L2).

pour le prédicat merge, tu prends deux listes et tu les fusionnes pour en faire une liste triée.
Quels sont les cas simples ? Une deux des deux listes est vide, donc la fusion est l'autre liste.

Code :

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

1
2
merge(X, [], X).
merge([], X, X).

C'est réglé pour ça.
Pour le reste, les deux listes ont au moins un élément, il suffit de les comparer, deux clauses sont donc à écrire. Je te laisse réfléchir.

PS il existe en SWI-Prolog un prédicat pour la longueur de liste, c'est length(?List, ?Int)

[patrick974]

Salut,
en effet, tu as raison, ca va bientot faire deux que j'ai appris a programmer, et j'ai commencer avec le c, puis le java. Je viens tout juste de commencer le prolog et j'avoue que c'est déroutant de ne pas utiliser de "while" ou de "for".
J'avais pensé a parcourrir la listes deux éléments par deux éléments en plaçant le premier à droite et le secong a gauche. Mais j'ai changé d'avis parce je n'avais pas envie de détrier les listes déja trié (maintenant je me suis rendu compte que c'était pas très malin puisque ca ne change rien au tps d'execution du code et que ce n'était pas non plus l'esprit prolog, merci ).
J'ai aussi fini par comprendre que je n'avais pas besoin de append non plus. Finalement, j'ai réussi à alléger mon code de façon considérable. Il est beaucoup plus court et beaucoup plus compréhensible.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
% Tri fusion
mergesort([],[]).
mergesort([X],[X]).
mergesort([X|Xs],Y) :-
    msplit([X|Xs],L1,L2),
    mergesort(L1,L1s),
    mergesort(L2,L2s),
    mmerge(L1s,L2s,Y).
mmerge([],X,X).
mmerge(X,[],X).
mmerge([X|Xs],[Y|Ys],[X|Zs]) :-
    X=<Y,!,
    mmerge(Xs,[Y|Ys],Zs).
mmerge([X|Xs],[Y|Ys],[Y|Zs]) :-
    X>Y,
    mmerge(Xs,Ys,Zs).
msplit([],[],[]).
msplit([X],[X],[]).
msplit([X1,X2|Xs],[X1|Ys],[X2|Zs]) :-
    msplit(Xs,Ys,Zs).

J'ai toujours un petit problème : la réponse donnée n'est pas unique. J'ai (je pense) une infinité de fois la même réponse. Après tout, ce n'est peut être pas si grave que ça (mais, pour moi la réponse sans les coupes-choix est fausse, c'est clair !), si je veux une solution unique, j'ajoute des coupes-choix ... Qu'en penses tu ? Est t'il possible ici, de faire sans les coupes choix ?
Merci.

[Trap D]

Tu es sûr de ton code ?
Il ne fonctionnne pas du tout :

1 ?- mergesort([10, 5, 4, 13, 20, 8, 12, 17, 6, 4, 25, 1], L).

L = [1, 8, 17] ;

L = [1, 8, 17] ;

L = [1, 8, 17]

[patrick974]

Bonjour,

Code :

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

1
2
3
4
 
mmerge([X|Xs],[Y|Ys],[Y|Zs]) :-
    X>Y,
    mmerge(Xs,Ys,Zs).

J'ai lancé la récursivité sur Xs au lieu de [X|Xs], du coup il y a des éléments qui sautent. J'ai testé la fonction avant de poster, et elle marchait, j'ai du faire une erreur de "bureautique", ou je sais pas ... dsl.
Je n'aurrai surment pas fait cette erreur si j'avais directement fait

Code :

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

1
2
3
 
mmerge(Xs,[Y|Ys],[Y|Zs]) :-
    mmerge(Xs,Ys,Zs).

en appliquant ce que tu m'a deja dit a propos des conditions qui s'annulent entre elles. Je crois que je vais essayer de l'appliquer systématiquement maintenant.
D'ou

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
% Tri fusion
mergesort([],[]).
mergesort([X],[X]).
mergesort([X|Xs],Y) :-
    msplit([X|Xs],L1,L2),
    mergesort(L1,L1s),
    mergesort(L2,L2s),
    mmerge(L1s,L2s,Y).
mmerge([],X,X).
mmerge(X,[],X).
mmerge([X|Xs],[Y|Ys],[X|Zs]) :-
    X=<Y,!,
    mmerge(Xs,[Y|Ys],Zs).
mmerge(Xs,[Y|Ys],[Y|Zs]) :-
    mmerge(Xs,Ys,Zs).
msplit([],[],[]).
msplit([X],[X],[]).
msplit([X1,X2|Xs],[X1|Ys],[X2|Zs]) :-
    msplit(Xs,Ys,Zs).

Mais le code est faux (sans les "coupe-choix") de toute façon, puisque j'ai pas unicité de la réponse. J'ai pourtant les cas les plus simples possibles comme condition d'arrêt. J'arrive pas a voir ce qui ne va pas.
Merci.

[Trap D]

Il y a quelquechose que tu dois comprendre au sujet des coupe-choix : ils sont parfois indispensables :

Code :

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

1
2
3
4
5
6
mergesort([X],[X]).
mergesort([X|Xs],Y) :-
    msplit([X|Xs],L1,L2),
    mergesort(L1,L1s),
    mergesort(L2,L2s),
    mmerge(L1s,L2s,Y).

tu écris mergesort([X],[X]). Bien la règle va réussir, pas de problème.
Mais n'oublie pas que Prolog travaille en étudiant toutes les solutions possibles, donc quand le backtracking va revenir à cet endroit, comme il n'y a pas de coupe-choix, Prolog va étudier la règle suivante, mergesort([X|Xs],Y) :- qui ici réussit avec Xs = [], et là tu vas te retrouver avec un problème de pile d'exécution ou de réponse multiple.

C'est le prof qui vous a dit de travailler sans copue-choix ?

[patrick974]

Bonjour,
ok, le fait d'avoir une condition d'arret et le cas qui "precede" cette condition d'arret aussi comme condition d'arret fait tourner le programme indefiniment (dans la pluart des cas on va dire). Maintenant je le sais.
Oui, c'est le prof qui nous l'a dit : "C'est très maladoit de programmer avec des coupe-choix", peut-être suis je un peu trop terre a terre, ou ... je sais pas.
Enfin, bref. J'ai compris toutes mes erreurs, je peux donc continuer a avancer.
Merci.
Au revoir.