CODEWITHSUNDEEP
prolog
Vortca 2
Vortca 2

Reputation: 41

Combine two lists without duplicates prolog

I'm writing a prolog homework that asks me to combine two lists together but without duplicates. For example combine([a, b, c], [c, d, e], Result).would give Result = [a, b, c, d, e].. But I'm getting Result = [a, b, c, c, d, e]. instead.

My code looks like this:

combine([Head|Tail], Lst2, [Head|Result]) :- 
    combine(Tail, Lst2, Result).

How would I be able to remove the duplicates here in the same rule, not using helper functions?

Upvotes: 0

Views: 680

Answers (2)

Nicholas Carey
Nicholas Carey

Reputation: 74317

Assuming that each source list constitutes an ordered set (e.g., it is both ordered and unique), you could simply merge them and discard dupes when you encounter them. Something like this:

merge( []     , []     , []     ).   % the merger of two empty lists is the empty list.
merge( [X|Xs] , []     , [X|Xs] ).   % the merger of a non-empty list and an empty list is the non-empty list
merge( []     , [Y|Ys] , [Y|Ys] ).   % the merger of an empty list and a non-empty list is the non-empty list
merge( [X|Xs] , [Y|Ys] , [X|Zs] ) :- % to merge two non-empty lists
  X @< Y,                            % and the left item is less than the right item
  merge( Xs, [Y|Ys], Zs )            % take the left item and recurse down
  .                                  %
merge( [X|Xs] , [Y|Ys] , [Y|Zs] ) :- % to merge two non-empty lists
  X @> Y,                            % and the left item is greater than the right item
  merge( [X|Xs], Ys, Zs )            % take the right item and recurse down
  .                                  %
merge( [X|Xs] , [Y|Ys] , [X|Zs] ) :- % to merge two non-empty lists
  X == Y,                            % and the left and right items are equal
  merge( Xs, Ys, Zs )                % take either item, discard the other and recurse down
  .                                  % Easy!

And if you wanted to keep the duplicates, you'd just need to modify the last clause for the == condition to push both X and Y onto the merged list.

Upvotes: 1

Reema Q Khan
Reema Q Khan

Reputation: 878

Try using member.

combine(List1,List2,CombinedList):-
combine1(List1,List2,List), %Return List with items not in List2
append(List,List2,AppendedList), %Join List and List2
sort(AppendedList,CombinedList). %Sort the final List

combine1([],_,[]).
combine1([H|T],List2,[H|L]):-
    \+member(H,List2),
    combine1(T,List2,L).
combine1([H|T],List2,L):-
    member(H,List2),
    combine1(T,List2,L).

Examples:

?- combine([a,b,d],[c],CombinedList).
CombinedList = [a, b, c, d]
false

?- combine([a,d,e],[c,b],CombinedList).
CombinedList = [a, b, c, d, e]
false

?- combine([],[c,b,a],CombinedList).
CombinedList = [a, b, c]

?-combine([a,b,c],[c,d,e],CombinedList).
CombinedList = [a, b, c, d, e]
false

Upvotes: 0

Related Questions