Przecięcie dwóch list bez duplikatów elementów w Prologu

Question

Potrzebuję napisać program, który znajdzie przecięcie dwóch list. Nie mogę używać cięć i nie powinno być żadnych duplikatów na liście wyników.

To jest mój kod:

intersection([],_,[]). 
intersection([X|Xs],Y,[X|Zs]) :- 
    member(X,Y), 
    intersection(Xs,Y,Zs). 
intersection([_|Xs],Y,Zs) :- 
    intersection(Xs,Y,Zs). 

Kiedy uruchomić następującą kwerendę uzyskać odpowiedzi na te pytania:

?- intersection([a,b,c,a],[a,v,c],L). 
L = [a, c, a] ; 
L = [a, c] ;   % <---------- this is only answer I want to get 
L = [a, a] ; 
L = [a] ; 
L = [c, a] ; 
L = [c] ; 
L = [a] ; 
L = []. 

Co mogę zrobić? Chcę uzyskać L = [a,c] i nic więcej ... Czy możesz pomóc?

Answer 1

Jeśli przez "koniunkcja" rozumiesz "przecięcie", powinieneś spojrzeć na implementację w SWI-Prolog library(lists) predykatu intersection/3. Zawiera cięcia, ale możesz je pominąć, jeśli nie masz nic przeciwko wszystkim punktom kontrolnym.

Dzięki niemu:

?- intersection([a,b,c,a],[a,v,c],I). 
I = [a, c, a]. 

Oczywiście, to nie działa nawet w orzecznik biblioteki, bo trzeba zestawy z aktualnej definicji. (Wystarczy, że tylko pierwszy argument jest zbiorem.)

Możesz tworzyć zestawy z predykatem sort/2: jeśli pierwszym argumentem jest lista z powtórzeniami, drugim argumentem będzie posortowana lista bez powtórzeń, na przykład :

?- sort([a,b,c,a], S1), intersection(S1, [a,v,c], I). 
S1 = [a, b, c], 
I = [a, c]. 

czy może:

?- sort([a,b,c,a], S1), intersection(S1, [a,v,c,c,a,c], I). 
S1 = [a, b, c], 
I = [a, c]. 

?- sort([a,b,c,a,b,c,a,b,c], S1), intersection(S1, [a,v,c,c,a,c], I). 
S1 = [a, b, c], 
I = [a, c]. 

Jeśli sortować oba argumenty, można użyć ord_intersection/3 z library(ordsets), realizowane w warunkach oset_int/3.

?- sort([a,b,c,a], S1), sort([a,v,c,c,a,c], S2), ord_intersection(S1, S2, I). 
S1 = [a, b, c], 
S2 = [a, c, v], 
I = [a, c]. 

Co ważne, oset_int/3 nie stosuje żadnych cięć w jego realizacji. Zakłada się jednak, że pierwszy i drugi argument są listami elementów posortowanych przez "standard order of terms" i bez duplikatów, jak to uczynił sort/2.

Jeśli z jakiegoś powodu nie chcesz używać sort/2, mógłbyś może korzystać z akumulatora i sprawdzić z nim przed podjęciem element do skrzyżowania:

my_intersection(Xs, Ys, Zs) :- 
    my_intersection_1(Xs, Ys, [], Zs). 
my_intersection_1([], _, Zs, Zs). 
my_intersection_1([X|Xs], Ys, Zs0, Zs) :- 
    member(X, Ys), \+ member(X, Zs0), 
    my_intersection_1(Xs, Ys, [X|Zs0], Zs). 
my_intersection_1([_|Xs], Ys, Zs0, Zs) :- 
    my_intersection_1(Xs, Ys, Zs0, Zs). 

oczywiście kolejność elementów w wyniku zostanie teraz odwrócony.Jeśli nie jest to, co masz na myśli przez „wspólnie”, można na przykład przerobić pierwsze dwie klauzule my_intersection_1/4 jak:

my_intersection_1([], _, _, []). 
my_intersection_1([X|Xs], Ys, Zs0, [X|Zs]) :- 
    member(X, Ys), \+ member(X, Zs0), 
    my_intersection_1(Xs, Ys, [X|Zs0], Zs). 

Answer 2

Wydaje się czymś takim byłby łatwy sposób:

intersection(Xs , Ys , Zs) :- 
    sort(Xs,X1)  , % order and de-dupe the 1st list so as to produce a set 
    sort(Ys,Y1)  , % order and de-dupe the 2nd list so as to produce a set 
    merge(Xs,Ys,Zs) % merge the two [ordered] sets to produce the result 
    .     % easy! 

merge([]  , []  , [] ) . 
merge([]  , [_|_] , [] ) . 
merge([_|_] , []  , [] ) . 
merge([X|Xs] , [Y|Ys] , [X|Zs]) :- X = Y , merge( Xs , Ys , Zs) . 
merge([X|Xs] , [Y|Ys] , Zs ) :- X < Y , merge( Xs , [Y|Ys] , Zs) . 
merge([X|Xs] , [Y|Ys] , Zs ) :- X > Y , merge([X|Xs] , Ys , Zs) . 

lub nawet tylko to [nie-strasznie-wydajnych] one-liner:

intersection(Xs , Ys , Zs) :- setof(Z,(member(Z,Xs),member(Z,Ys)),Zs). 

Answer 3

W my answer do powiązanego pytanie "Intersection and union of 2 lists" przedstawiłem logicznie czystego pre dikodowy list_list_intersectionSet/3. Powinien pasować do twoich wymagań do T!

Oto jest wersja szczotkowane-up list_list_intersectionSet/3, która opiera się na:

• monotonia warunkowy if_/3,
• meta-predicatetfilter/3,
• a reified Test predykaty dif/3 i memberd_t/3.

Zaczynamy:

list_list_intersectionSet([]  ,_ ,[]). 
list_list_intersectionSet([A|As0],Bs,Cs0) :- 
    if_(memberd_t(A,Bs), Cs0 = [A|Cs], Cs0 = Cs), 
    tfilter(dif(A),As0,As), 
    list_list_intersectionSet(As,Bs,Cs). 

Zobaczymy go w akcji!

?- list_list_intersectionSet([a,b,c,a],[a,v,c],L). 
L = [a,c]. 

Answer 4

Wcześniej pokazano list_list_intersectionSet/3ogranicza kolejność pozycja na skrzyżowaniu:

 
?- list_list_intersectionSet([a,b],[a,b], [a,b]). 
true. 

?- list_list_intersectionSet([a,b],[a,b], [b,a]). 
false. 

W tej odpowiedzi podnosimy takie ograniczenie ... konserwujący logical-purityi determinizm (dla spraw gruntowych)!

Najpierw definiujemy none_intersect/2 użyciu Prolog lambdas i meta-predicatemaplist/2.

none_intersect(As,Bs) stwierdza, że ​​wszyscy członkowie w As różnią się od wszystkich członków w Bs.

:- use_module(library(lambda)). 

none_intersect(As,Bs) :- 
    maplist(\A^maplist(dif(A),Bs),As). 

Następnie definiujemy intersection_of_and/3 --- podstawie none_intersect/2 (zdefiniowany powyżej), meta-predicatetpartition/4 i reified równości termin (=)/3:

intersection_of_and([],As,Bs) :- 
    none_intersect(As,Bs). 
intersection_of_and([X|Xs],As0,Bs0) :- 
    tpartition(=(X),As0,[_|_],As),  % [_|_] = [X|_] 
    tpartition(=(X),Bs0,[_|_],Bs),  % [_|_] = [X|_] 
    intersection_of_and(Xs,As,Bs). 

intersection_of_and(Xs,As,Bs) stany że

• wszystkie elementy, które występują zarówno w As i Bs występują również w Xs (pierwszy punkt),
• wszystkie pozycje w Xs występować zarówno As i Bs przynajmniej raz (drugi punkt),
• a lista Xs nie zawiera żadnych duplikatów.

intersection_of_and/3 używa określonego argumentu w celu włączenia indeksowania pierwszego argumentu.

Ostatni definiujemy list_list_intersection/3 który ma porządek argument, że PO używany:

 
list_list_intersection(As,Bs,Xs) :- 
    intersection_of_and(Xs,As,Bs). 

Uciekajmy kilka pytań! Po pierwsze, zapytanie, że oferentem Bounty zasugerował:

 
?- list_list_intersection([a,b],[a,b], [b,a]). 
true. 

Następny podobny zapytania z 3 odrębnych elementów w 3 list o 3 różnych zleceń:

?- list_list_intersection([a,b,c],[b,a,c], [c,a,b]). 
true. 

Co jeśli niektóre x występuje tylko w pierwszym/druga lista?

 
?- list_list_intersection([a,b,c,x],[b,a,c], [c,a,b]). 
true. 

?- list_list_intersection([a,b,c],[b,a,c,x], [c,a,b]). 
true. 

Co się stanie, jeśli jakaś pozycja pojawi się dwukrotnie na pierwszej/drugiej liście?

 
?- list_list_intersection([a,b,c],[b,a,c,b], [c,a,b]). 
true. 

?- list_list_intersection([a,b,c,c],[b,a,c], [c,a,b]). 
true. 

Wreszcie, co jeśli skrzyżowanie zawiera duplikaty? Skrzyżowania nie są zawierać duplikaty ...

 
?- list_list_intersection([a,b,c],[b,a,c], [c,c,a,b]). 
false.          % as expected 

Answer 5

ten może być rozwiązany poprzez zwykłe teorii mnogości:

intersection(A,B,AnB):- 
     subtract(A,B,AminusB), 
     subtract(A,AminusB,K), 
     sort(K,AnB). 

dla zapytania:

?- intersection([a,b,c,a],[a,v,c],L). 

wyjście jest

L = [a, c]. 

Brak odpowiedzi.