Intersection et l'union de 2 listes

je suis le démarrage de l'apprentissage prologue (j'utilise SWI-prolog) et j'ai fait un simple exercice dans lequel j'ai 2 listes et je veux calculer leur intersection et d'union.
Voici mon code qui fonctionne assez bien, mais je me demandais si il ya une meilleure façon de le faire, car je n'aime pas utiliser le COUPE de l'opérateur.

intersectionTR(_, [], []).
intersectionTR([], _, []).
intersectionTR([H1|T1], L2, [H1|L]):-
    member(H1, L2),
    intersectionTR(T1, L2, L), !.
intersectionTR([_|T1], L2, L):-
    intersectionTR(T1, L2, L).

intersection(L1, L2):-
    intersectionTR(L1, L2, L),
    write(L).


unionTR([], [], []).
unionTR([], [H2|T2], [H2|L]):-
    intersectionTR(T2, L, Res),
    Res = [],
    unionTR([], T2, L),
    !.
unionTR([], [_|T2], L):-
    unionTR([], T2, L),
    !.

unionTR([H1|T1], L2, L):-
    intersectionTR([H1], L, Res),
    Res \= [],
    unionTR(T1, L2, L).
unionTR([H1|T1], L2, [H1|L]):-
    unionTR(T1, L2, L).

union(L1, L2):-
    unionTR(L1, L2, L),
    write(L).

Gardez à l'esprit que je veux avoir juste 1 résultat, pas de résultats multiples (même si elle est correcte) si l'exécution du code avec ceci:

?- intersect([1,3,5,2,4] ,[6,1,2]).

devrait quitter avec:

[1,2]
true.

et pas avec

[1,2]
true ;
[1,2]
true ;
etc...

La même chose doit être valable pour l'union prédicat.
Comme je l'ai dit, mon code fonctionne assez bien mais s'il vous plaît suggérer de meilleures façons de le faire.
Grâce

OriginalL'auteur andreapier | 2012-03-08

list prolog

6

Aussi, vous ne savez pas pourquoi vous êtes mort contre les coupures, tant que leur suppression ne modifie pas la declaritive sens du code, comme par votre lien. Par exemple:
```
inter([], _, []).

inter([H1|T1], L2, [H1|Res]) :-
    member(H1, L2),
    inter(T1, L2, Res).

inter([_|T1], L2, Res) :-
    inter(T1, L2, Res).

test(X):-
        inter([1,3,5,2,4], [6,1,2], X), !.

test(X).
X = [1, 2].
```
Dans les bits d'essai où j'ai appeler le code, je dis juste que ne l'intersection, mais je suis seulement intéressé dans la première réponse. Il n'y a pas de coupures dans le prédicat définitions elles-mêmes.

Je vais accepter cette réponse car elle est la plus correcte. Après une enquête plus approfondie, j'ai compris que ce que j'ai demandé n'est tout simplement pas possible sans les COUPER, en raison de la non-déterminisme. Et oui, à l'aide de la COUPER de cette façon, ne modifie pas la nature déclarative du programme. Merci beaucoup!
andreapier: Il n'est pas besoin de couper, de voir une autre réponse!
test([]). incorrectement réussit.

OriginalL'auteur magus
6

La liste suivante est basée sur mon réponse précédente à Supprimer les doublons dans la liste (Prolog);
l'idée de base est, à son tour, repose sur @fausse réponse à Prologue de l'union pour Un U B U C.

Quel est le message que je veux transmettre à vous?
- Vous pouvez décrire ce que vous voulez dans le Prologue avec logique de pureté.
- À l'aide de if_/3 et (=)/3 une logique pure de la mise en œuvre peut être
  - à la fois efficace (en laissant derrière des points de choix uniquement lorsque cela est nécessaire)
  - et monotone (logiquement son à l'égard de généralisation /spécialisation).
- La mise en œuvre de @faux de prédicats if_/3 et (=)/3 ne utiliser les méta-logique Prolog fonctionnalités en interne, mais (de l'extérieur) se comporte logiquement pur.
La suite de la mise en œuvre de list_list_intersection/3 et list_list_union/3 utilise list_item_isMember/3 et list_item_subtracted/3, définies dans un réponse précédente:
```
list_list_union([],Bs,Bs).
list_list_union([A|As],Bs1,[A|Cs]) :-
    list_item_subtracted(Bs1,A,Bs),
    list_list_union(As,Bs,Cs).

list_list_intersection([],_,[]).
list_list_intersection([A|As],Bs,Cs1) :-
    if_(list_item_isMember(Bs,A), Cs1 = [A|Cs], Cs1 = Cs),
    list_list_intersection(As,Bs,Cs).
```
Voici la requête que vous avez posté en tant que partie de votre question:
```
?- list_list_intersection([1,3,5,2,4],[6,1,2],Intersection).
Intersection = [1, 2].                    % succeeds deterministically
```
Essayons autre chose... Les deux requêtes suivantes devraient être logiquement équivalentes:
```
?- A=1,B=3, list_list_intersection([1,3,5,2,4],[A,B],Intersection).
A = 1,
B = 3,
Intersection = [1, 3].
?- list_list_intersection([1,3,5,2,4],[A,B],Intersection),A=1,B=3.
A = 1,
B = 3,
Intersection = [1, 3] ;
false.
```
Et... la ligne de fond est?
- Avec code pur, il est facile de rester sur le côté de la logique de la solidité.
- Impur code, d'autre part, le plus souvent, agit comme "il fait ce qu'il doit" à première vue, mais montre tous les types de comportement illogique avec des requêtes comme celles montrées ci-dessus.
Modifier 2015-04-23

Ni list_list_union(As,Bs,Cs) ni list_list_intersection(As,Bs,Cs) garantir que Cs ne contient pas de doublons. Si cela vous ennuie, le code doit être adapté.

Voici quelques plus de questions (et réponses) avec As et/ou Bs contenant des doublons:
```
?- list_list_intersection([1,3,5,7,1,3,5,7],[1,2,3,1,2,3],Cs).
Cs = [1, 3, 1, 3].
?- list_list_intersection([1,2,3],[1,1,1,1],Cs).
Cs = [1].

?- list_list_union([1,3,5,1,3,5],[1,2,3,1,2,3],Cs).
Cs = [1, 3, 5, 1, 3, 5, 2, 2]. 
?- list_list_union([1,2,3],[1,1,1,1],Cs).
Cs = [1, 2, 3].
?- list_list_union([1,1,1,1],[1,2,3],Cs).
Cs = [1, 1, 1, 1, 2, 3].
```
Modifier 2015-04-24

Par souci d'exhaustivité, voici comment on pourrait faire valoir que l'intersection et l'union sont des ensembles---c'est les listes qui ne contiennent pas tous les éléments en double.

Le code suivant est assez simple:
```
list_list_intersectionSet([],_,[]).
list_list_intersectionSet([A|As1],Bs,Cs1) :-
    if_(list_item_isMember(Bs,A), Cs1 = [A|Cs], Cs1 = Cs),
    list_item_subtracted(As1,A,As),
    list_list_intersectionSet(As,Bs,Cs).

list_list_unionSet([],Bs1,Bs) :-
    list_setB(Bs1,Bs).
list_list_unionSet([A|As1],Bs1,[A|Cs]) :-
    list_item_subtracted(As1,A,As),
    list_item_subtracted(Bs1,A,Bs),
    list_list_unionSet(As,Bs,Cs).
```
Noter que list_list_unionSet/3 est basé sur list_setB/2, défini ici.

Maintenant, nous allons voir les deux list_list_intersectionSet/3 et list_list_unionSet/3 en action:
```
?- list_list_unionSet([1,2,3,1,2,3,3,2,1],[4,5,6,2,7,7,7],Xs).
Xs = [1, 2, 3, 4, 5, 6, 7].

?- list_list_intersectionSet([1,2,3,1,2,3,3,2,1],[4,5,6,2,7,7,7],Xs).
Xs = [2].
```
Modifier 2019-01-30

Voici une requête supplémentaire de prises de @GuyCoder commentaire (plus de deux variantes de celui-ci):
```
?- list_list_unionSet(Xs,[],[a,b]). 
Xs = [a,b] 
; Xs = [a,b,b] 
; Xs = [a,b,b,b] 
... 

?- list_list_unionSet([],Xs,[a,b]). 
Xs = [a,b] 
; Xs = [a,b,b] 
; Xs = [a,b,b,b] 
... 

?- list_list_unionSet(Xs,Ys,[a,b]). 
Xs = [], Ys = [a,b] 
; Xs = [], Ys = [a,b,b] 
; Xs = [], Ys = [a,b,b,b] 
... 
```
Avec l'ancienne version de list_item_subtracted/3, au-dessus de requêtes n'a pas résilier le plan existentiel.

Avec la nouvelle qu'ils font.
Comme l'ensemble des solutions est de taille infinie, aucune de ces requêtes mettre fin à universellement.

Est-ce suppose de travailler? list_list_unionSet(A,[],[a,b]).
Merci! Devrait être (légèrement) mieux maintenant. Pour info la référence "réponse précédente" a été édité.

OriginalL'auteur repeat
2

De tricher un peu moins de ma première réponse, vous pouvez utiliser le findall d'ordre supérieur prédicat qui obtient Prologue à faire de la récursivité pour vous :
```
4 ?- L1=[1,3,5,2,4], L2=[6,1,2], findall(X, (nth0(N, L1, X), member(X, L2)), Res).
L1 = [1, 3, 5, 2, 4],
L2 = [6, 1, 2],
Res = [1, 2].
```
OriginalL'auteur magus

Si le but est juste "faire le travail", puis swi prolog a construit dans les primitives pour exactement cet effet:

[trace] 3 ?- intersection([1,3,5,2,4] ,[6,1,2], X).
intersection([1,3,5,2,4] ,[6,1,2], X).
X = [1, 2].

[trace] 4 ?- union([1,3,5,2,4] ,[6,1,2], X).
X = [3, 5, 4, 6, 1, 2].

OriginalL'auteur magus

-1

Et, enfin, (vraiment), vous pouvez utiliser findall pour trouver toutes les solutions, puis utilisez nth0 pour extraire la première, ce qui vous donnera le résultat que vous souhaitez, sans coupure, et garde les prédicats agréable et propre, sans d'autres prédicats piège/stop prologue de faire ce qu'il fait de mieux - revenir en arrière et trouver des réponses multiples.

Edit: Il est permis de penser que la mise en supplémentaires de prédicats dans la "logique de base" pour éviter de multiples résultats générés, est le plus laid/à confusion en utilisant les réductions que vous essayez d'éviter. Mais c'est peut-être un exercice académique de prouver qu'il peut être fait sans l'aide de prédicats d'ordre supérieur comme findall, ou le haut-ins intersection/union.
```
inter([], _, []).

inter([H1|T1], L2, [H1|Res]) :-
    member(H1, L2),
    inter(T1, L2, Res).

inter([_|T1], L2, Res) :-
    inter(T1, L2, Res).

test(First):-
        findall(Ans, inter([1,3,5,2,4], [6,1,2], Ans), Ansl), 
        nth0(0, Ansl, First).
```
OriginalL'auteur magus
-1

Je sais que ce post est très vieux, mais j'ai trouvé une solution avec un minimum de codage.

% d'intersection
intersection([],L1,L2,L3).
intersection([H|T],L2,L3,[H|L4]):-membre(H,L2),intersection(T,L3,L3,L4).
% membre
membre(H,[H|T]).
membre(X,[H|T]):-membre(X,T).

Pour tester le code ci-dessus, vous ne devriez pas entrer en L3. Voici un des exemples.

?- intersection([w,4,g,0,v,45,6],[x,45,d,w,30,0],L).
L = [w, 0, 45].

J'ai remarqué que j'ai été l'aide de l'intersection de la méthode. si ce code ne fonctionne pas.

OriginalL'auteur Saeid Zarrinmehr
-2

% De l'élément X dans la liste?

pert(X, [ X | _ ]).

pert(X, [ _ | L ]):- pert(X, L).

% De l'Union de deux de la liste

de l'union([ ], L, L).

de l'union([ X | L1 ], L2, [ X | L3 ]):- \+pert(X, L2), union(L1, L2, L3).

de l'union([ _ | L1 ], L2, L3):- union(L1, L2, L3).

% Intersection de deux liste

inter([ ], _, [ ]).

inter([ X | L1 ], L2, [ X | L3 ]):- pert(X, L2), l'inter(L1, L2, L3).

inter([ _ | L1 ], L2, L3):- inter(L1, L2, L3).

OriginalL'auteur jlcdev

Vous devez vous connecter pour publier un commentaire.

Modifier 2015-04-23

Modifier 2015-04-24

Modifier 2019-01-30