etre_avant dans une liste [Résolu]

[sologne]

Bonjour,

je cherche à savoir comment on fait pour savoir dans une liste si un élément est avant un autre.
J'ai rédige cela :

Code :

1
2
3
est_avant(A, B, [A, B | _]).
est_avant(A, B, [_ | Y]) :- est_avant(A, B, Y).

qui fonctionne correctement si A est juste avant B dans la liste, mais pas si il y a des éléments entre A et B.

Avez vous des idées pour améliorer ce début de code ?

[Trap D]

Oui, as-tu entendu parler de append ?
Si oui, réfléchis bien à son utilisation.

[sologne]

Bonjour Trap D,

merci à toi de t'être intéressé à mon pb. D'après ce que j'ai vu la fonction "append" permet de réaliser des concaténations de listes, et étant débutant dans ce langage, je ne vois pas comment en détourner l'usage pour résoudre mon pb...
D'un point de vu algorithmique, et avec un langage 'classique' : Java, C, php cela ne me poserai aucun souci. je ferai une implémentation de type :

Code :

1
2
3
4
5
6
7
8
9
10
function est_avant(A, B, Liste) : bool {
 int IndA = indexe(A,Liste); // la fonction indexe étant déjà implémenté
 int IndB = indexe(B,Liste);
   if(IndA <  IndB) {
      return true;
   } else {
      return false;
   }
}

Voila, ce n'est pas de la mauvaise volonté et j'ai l'habitude de coder mais l'apprentissage de prolog est assez déroutant lorsque l'on vient des langages 'clasiques'.

Pourrais-tu stp m'éclairer un peu plus ?

[Trap D]

Voilà bien ce qui est ennuyeux quand on vient d'un langage impératif, on est formaté par ce type de raisonnement et ça ne marche pas du tout avec Prolog. Ne t'en fais pas, cela viendra, mais il faut persister, je suis aussi passé par la.
Pour t'éclairer sur le mode de raisonnement : si l'élément A est avant B dans la liste L, cela veut d'abord dire qu'il existe une sous-liste de L qui commence par A, donc on peut écrire

Code :

append(_, [A | X], L)

je pense que tu connais la signification du '_'.
Maintenant, je te laisse terminer : si B est après A dans L, cela veut dire qu'il existe ...
En Prolog, au début, il faut éviter toute considération d'efficacité de code, cela viendra après, quand tu commenceras à comprendre le mécanisme de réflexion.

[sologne]

Bonjour TrapD,

J'ai eu beau chercher dans la direction que tu m'indiques et malheureusement je n'arrive pas à aboutir ...

Par contre j'ai fini par réussir à écrire ce bout de code qui répond à mon problème.

Code :

1
2
3
4
5
6
7
8
9
10
11

rang(X,[X|Q],0).
rang(X,[T|Q], Somme) :-
  rang(X,Q,S),
  Somme is S+1.
  
estavant(A, B, Liste):-
	rang(A,Liste,RangA),
	rang(B,Liste,RangB),
	RangA < RangB.

mais qui est fortement inspiré de l'algo écrit dans mon post précédent et qui s'éloigne à mon sens de l'esprit de prolog ...

Ayant trouvé une solution, certes pas la meilleurs, acceptes-tu de me communiquer la solution que tu proposes avec le append ?

[Trap D]

Ben, elle est "toute simple" :

Code :

1
2
3
4
5
est_avant(A, B, L) :-
        % il existe une sous-liste de L qui commence par A,
	append(_, [A | X], L),
       % il existe une sous-liste de X qui commence par B,
	append(_, [B | _], X ).

[sologne]

En effet,

une fois que l'on voit la solution c'est simple : j'ai du chemin à parcourir, pour rentrer dans cet esprit...

Merci de ton aide précieuse.