Tri de sélection dans prolog

Je suis nouveau dans Prolog et j'essaie de faire trier la sélection. Voici ce que j'ai:Tri de sélection dans prolog

ssort([],[]). 
ssort([M|S],L):-min(M,L),remove(M,L,N),ssort(S,N). 

min(M,[M]). 
min(M,[H,T]):-min(N,T),min2(M,H,N). 

min2(A,A,B):-less(A,B). 
min2(B,A,B):-not(less(A,B)). 

less(A,B):-(A<B). 

append([],B,B). 
append([H|A],B,[H|AB]):-append(A,B,AB). 

remove(X,L,N):-append(A,[X|B],L),append(A,B,N).

Mais quand j'essaie ceci par exemple:

ssort(S,[5,3,1]),write(S).

Je me false, peu importe ce que j'essaie. Pouvez-vous me dire comment je peux trier la liste et obtenir le résultat écrit en S?

Source

2017-03-19 Petar D.

L'avez-vous tracé? Triez-vous le premier ou le deuxième argument? Avez-vous essayé de tester chacun des prédicats de façon isolée? Par exemple, êtes-vous sûr que votre 'min/2' fait ce que vous attendez de faire? Je demande parce que vous pourriez être capable de résoudre votre problème par vous-même sans trop d'effort, et parce que si j'essayais de faire un tri de sélection dans Prolog, ce serait un peu trop différent de ce que vous avez en ce moment, et c'est un travail désagréable pour traquer les erreurs des autres ("bugs"). –

Malheureusement, je ne sais pas comment le tracer. Je trie le deuxième argument, et écrit le résultat dans le premier. 'min2' est supposé trouver le minimum entre le 2ème et le 3ème argument et l'écrire dans le premier. Je ne suis pas sûr si je le fais bien, cependant: D –

Voici une suggestion: tester votre 'min/2' et votre' min2/3'. Si elles fonctionnent comme prévu, vous avez un problème ailleurs (et il n'y a pas beaucoup de code). Si elles ne fonctionnent pas comme prévu, vous pouvez poser une question plus petite et plus précise, plus facile à répondre. En ce moment vous avez juste un tas de code et "corrigez-le s'il vous plaît" ce qui n'est pas une bonne approche à demander. –

Comme l'a bien souligné @Boris, l'erreur principale était dans le prédicat min/2 car il nécessite un 3ème paramètre pour retourner l'élément min dans ce paramètre. Avec quelques petits changements que le code ressemble à:

ssort([],[]). 
ssort([M1|S],[H|T]):-min(H,T,M1),remove(M1,[H|T],N),ssort(S,N). 

min(M,[],M). 
min(M,[H|T],M1):-min2(M,H,N),min(N,T,M1). 

min2(A,B,A):-less(A,B). 
min2(A,B,B):-not(less(A,B)). 

less(A,B):-(A<B). 

append([],B,B). 
append([H|A],B,[H|AB]):-append(A,B,AB). 

remove(X,L,N):-append(A,[X|B],L),append(A,B,N).

Exemple:

?- ssort(S,[5,3,1]). 
S = [1, 3, 5] ; 
false. 

?- ssort(S,[5,3,1,7]). 
S = [1, 3, 5, 7] ; 
false.

EDIT:

Comme @Will Ness a juste titre la seule erreur était la virgule en min(M,[H,T]) donc en changeant en min (M, [H | T]) ça marche bien !!! Je pensais que le prédicat min/2 ne fonctionnait pas très bien donc je l'ai changé dans la réponse ci-dessus mais finalement ce n'était pas nécessaire.

Source

2017-03-19 13:47:14 coder

Que se passe-t-il si vous essayez 'ssort (Sorted, [1,2,1])'? –

@Boris, j'ai (déjà) remarqué que lorsqu'il y a des éléments en double il y a des réponses en double, par exemple ssort (Sorted, [1,2,1,1]) renvoie 6 mêmes réponses correctes car il y a des façons de mettre les trois 1-éléments au début de la liste triée (3 façons pour la 1ère position, 2 pour la seconde et 1 pour la troisième donc globalement 3 * 2 * 1 = 6 façons) ... Je pense que cela est dû au prédicat min2/2 mais de toute façon il ne donne pas de mauvaises réponses ... les doublons peuvent être supprimés avec l'opérateur de coupe ... – coder

Merci pour les réponses. Une dernière chose, pourquoi faites-vous référence au prédicat 'min' comme' min/2'? –

Voici comment vous pouvez au moins localiser l'erreur dans votre programme. Si votre requête échoue, supprimez simplement les objectifs de votre programme. Si le fragment restant échoue toujours, il doit y avoir une erreur dans ce fragment.

 
:- op(950,fy,*). 
*_. 

ssort(_/*[]*/,[]). 
ssort(_/*[M|S]*/,L):- 
    min(_/*M*/,L), 
    * remove(M,L,N), 
    * ssort(S,N). 

min(M,[M]). 
min(M,[H,T]):- 
    * min(N,T), 
    * min2(M,H,N). 

?- ssort(S,[5,3,1]).

Parce que ce fragment échoue, votre programme d'origine échouera également. Vous devez généraliser quelque chose dans la partie restante.

Source

2017-03-19 14:41:15 false

Tri de sélection dans prolog

Répondre

Questions connexes