Пересечение и объединение 2 списков

Question

Я начинаю изучать пролог (я использую SWI-пролог), и я выполнил простое упражнение, в котором у меня есть 2 списка, и я хочу вычислить их пересечение и объединение. Вот мой код, который работает довольно хорошо, но я спрашивал себя, есть ли лучший способ сделать это, так как я не люблю использовать оператор CUT.

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).

Имейте в виду, что я хочу получить только 1 результат, а не несколько результатов (даже если они правильные), поэтому запустите код с этим:

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

должен выйти с:

[1,2]
true.

а не с

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

То же самое должно быть действительным для предиката объединения.
Как я уже сказал, мой код работает довольно хорошо, но, пожалуйста, предложите лучшие способы сделать это.
Спасибо

Answer 1

Кроме того, не уверен, почему вы мертвы против сокращений, до тех пор, пока их удаление не изменит переводное значение кода согласно вашей ссылке. Например:

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].

В тестовом бите, где я вызываю код, я просто говорю, сделайте пересечение, но меня интересует только первый ответ. Нет никаких сокращений в самих определениях предикатов.

Answer 2

Следующее основано на моем предыдущем ответе " Удалить дубликаты в списке" (Пролог); основная идея, в свою очередь, основана на ответе @false профсоюзу Prolog для AUBUC.

Какое сообщение я хочу донести до вас?

• Вы можете описать, что вы хотите в Прологе с логической чистотой.
• С помощью if_/3 а также (=)/3 логически чистая реализация может быть
  • оба эффективны (оставляя позади точки выбора только при необходимости)
  • и монотонный (логически обоснованный в отношении обобщения / специализации).
• Реализация предикатов @false if_/3 а также (=)/3 действительно использует мета-логические функции Пролога внутренне, но (извне) ведет себя логически чисто.

Следующая реализация list_list_intersection/3 а также list_list_union/3 использования list_item_isMember/3 а также list_item_subtracted/3, определенный в предыдущем ответе:

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).

Вот запрос, который вы разместили как часть вашего вопроса:

?- list_list_intersection([1,3,5,2,4],[6,1,2],Intersection).
Intersection = [1, 2].                    % succeeds deterministically

Давайте попробуем что-нибудь еще... Следующие два запроса должны быть логически эквивалентны:

?- 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.

И... суть в том, что?

• С чистым кодом легко оставаться на стороне логической обоснованности.
• С другой стороны, нечистый код чаще всего действует с первого взгляда как "он делает то, что должен", но демонстрирует все виды нелогичного поведения с запросами, подобными приведенным выше.

---

Редактировать 2015-04-23

ни list_list_union(As,Bs,Cs) ни list_list_intersection(As,Bs,Cs) гарантировать, что Cs не содержит дубликатов. Если это вас беспокоит, код необходимо адаптировать.

Вот еще несколько запросов (и ответов) с As и / или Bs содержащие дубликаты:

?- 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].

---

Редактировать 2015-04-24

Для полноты картины, вот как мы могли бы обеспечить, чтобы пересечение и объединение были множествами, то есть списками, которые не содержат повторяющихся элементов.

Следующий код довольно прост:

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).

Обратите внимание, что list_list_unionSet/3 основывается на list_setB/2, определенный здесь.

Теперь давайте посмотрим, как list_list_intersectionSet/3 а также list_list_unionSet/3 В бою:

?- 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].

Answer 3

Чтобы обмануть чуть меньше моего первого ответа, вы можете использовать предикат findall высшего порядка, который заставляет Prolog выполнить рекурсию за вас:

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].

Answer 4

Если цель состоит в том, чтобы просто "выполнить работу", то swi prolog встроил примитивы именно для этой цели:

[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].

Answer 5

Попробуйте это, аналог union/3 здесь:

      :- use_module(library(clpfd)).

member(_, [], 0).
member(X, [Y|Z], B) :-
   (X #= Y) #\/ C #<==> B,
   member(X, Z, C).

intersect([], _, []).
intersect([X|Y], Z, T) :-
   freeze(B, (B==1 -> T=[X|R]; T=R)),
   member(X, Z, B),
   intersect(Y, Z, R).

Это работает, если элементы являются целыми и не оставляют точки выбора:

      ?- intersect([X,Y],[Y,Z],L).
freeze(_15070,  (_15070==1->L=[X, Y];L=[Y])),
_15070 in 0..1,
_15166#\/_15168#<==>_15070,
_15166 in 0..1,
X#=Y#<==>_15166,
X#=Z#<==>_15168,
Y#=Z#<==>_15258,
_15168 in 0..1,
_15258 in 0..1.

?- intersect([X,Y],[Y,Z],L), X=1, Y=2, Z=3.
X = 1,
Y = 2,
Z = 3,
L = [2].

?- intersect([X,Y],[Y,Z],L), X=3, Y=2, Z=3.
X = Z, Z = 3,
Y = 2,
L = [3, 2].

Answer 6

Я знаю, что этот пост очень старый, но я нашел решение с минимальным кодированием.

% пересечение пересечение ([],L1,L2,L3). Пересечение ([H|T],L2,L3,[H|L4]):- член (Н,L2), пересечение (Т,L3,L3,L4). % член (H,[H|T]). Член (Х,[H|T]):- Член (X, Т).

Для проверки вышеуказанного кода не следует вводить L3. Вот примеры.

? - пересечение ([w,4,g,0,v,45,6],[x,45,d,w,30,0],L). L = [w, 0, 45].

Answer 7

И наконец (действительно), вы можете использовать findall, чтобы найти все решения, затем использовать nth0, чтобы извлечь первое, которое даст вам желаемый результат без сокращений, и сохранит предикаты красивыми и чистыми, без каких-либо дополнительных предикатов для ловушка / стоп пролог делает то, что умеет лучше всего - откатывает назад и находит несколько ответов.

Редактировать: Можно утверждать, что добавление дополнительных предикатов в "основную логику" для предотвращения создания нескольких результатов столь же безобразно / запутанно, как и использование сокращений, которых вы пытаетесь избежать. Но, возможно, это академическое упражнение, чтобы доказать, что это можно сделать без использования предикатов более высокого порядка, таких как findall или встроенное пересечение / объединение.

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).

Answer 8

% Элемент X находится в списке?

Перт (X, [X | _]).

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

% Союз двух списков

союз ([], L, L).

объединение ([ X | L1 ], L2, [ X | L3 ]):- \+pert(X, L2), объединение (L1, L2, L3).

объединение ([_ | L1], L2, L3): - объединение (L1, L2, L3).

% Пересечение двух списков

Интер ([], _, []).

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

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