[Prolog] Echanger deux sous-listes

Dev
1

Le but est d’apparence simple : on a une liste L contenant une sous-liste S1. Il faudrait parvenir à échanger S1 avec une seconde sous-liste S2, le tout en SWI-Prolog. Depuis plusieurs jours, je me prends la tête avec un collègue à essayer de trouver une solution à ce problème sans voir comment faire.
Pour mémoire, [3,4] est une sous-liste de [1,2,3,4], mais pas de [1,2,3,5,4] pas plus que [4,3] n’est une sous-liste de [1,2,3,4]. Mais bon ça j’ai déjà trouvé les prédicats pour s’assurer que ça marche bien.

Evidemment, il ne semble pas possible de cumuler deux fonctions à la fois genre

Mais si vous avez un moyen pour le faire correctement et comme on pourrait le faire dans un langage plus commun, je suis tout aussi preneur.

Merci de votre aide.

2

Ah du Prolog, ça faisait longtemps :stuck_out_tongue:

Bon alors j’ai fait ça en vitesse, c’est sûrement pas optimisé mais ça a l’air de marcher, donc si ça peut t’aider:

[code]/* miroir(L1,L2) : renverse la liste L1 */
miroir(X, R) :- miroir(X, [], R).
miroir([], R, R).
miroir([X|L], A, R) :- miroir(L, [X|A], R).

/* sousListeTete(L,SL,Q) : si SL est une sous-liste de tête de L, Q reçoit le reliquat (donc la queue de L) */
sousListeTete([],Q,Q).
sousListeTete([X|SL], [X|L], Q) :- sousListeTete(SL,L, Q).

/* coupeListe(L,SL,T,Q) : cherche la sous-liste SL dans L, puis coupe L pour extraire la tête et la queue */
coupeListe(L,SL,T,Q) :- coupeListe(L,SL,[],R,Q), miroir(R,T).
coupeListe(L,SL,R,R,Q) :- sousListeTete(SL,L,Q), !.
coupeListe([X|L],SL,A,R,Q) :- coupeListe(L,SL, [X|A],R,Q).

/* echangeSousListes(L,SL1,SL2,R) : remplace SL1 par SL2 dans L */
echangeSousListes(L,SL1,SL2,R) :- coupeListe(L,SL1,T,Q), append(T,SL2,TEMP), append(TEMP,Q,R).[/code]

3

Je vais voir ça, merci. Je sens que je vais détester ce langage moi…

4

On sera deux :stuck_out_tongue:

5

En fait, j’ai du mal à me faire à la logique de ce langage. Sans compter que penser que ce truc là teste toutes les solutions possibles, ça me fait un peu frémir niveau complexité.

Pour en revenir à mon problème, un collègue m’a montré une solution à base de 4 appends habilement faits qui permettent de dire si en remplaçant la sous-liste S1 de la liste L1 par la sous-liste S2 de la liste L2 dans L1 on obtenait L2.
Bref : Soient L1 = [DebutL1,S1,FinL1] et L2 = [DebutL2,S2,FinL2], est-ce que [DebutL1,S2,FinL1] = L2 ?

C’était le but original de la question, mais je pensais qu’en trouvant si possible un prédicat simple pour échanger deux sous listes, le problème pourrait être résolu, d’où ma question initiale pour extraire une sous-liste.

Du coup, la solution devient quelque chose comme ça :

rempl(S1,S2,L1,L2):-append(DS1, Fin, L1), append(Debut, S1, DS1), append(Debut, S2, DS2), append(DS2, Fin, L2).

J’ai tout de même l’impression que dans certains cas, ce langage pourrait faciliter le travail du programmeur, de façon ponctuelle. Heureusement on peut l’intégrer à Java et d’autres trucs plus utilisés, ce qui me semble être la seule finalité de ce genre de langages.

Merci de ton aide Soltan.