0

The list with repetition consists of the elements (element, number_of_occurrences). For two lists of such elements find the intersection.

I wrote the following code

min(X,Y,X):-X=<Y.
min(X,Y,Y):-X>Y.

search([X,Y],[[X,W]|_],[X,Z]):-min(Y,W,Z).
search([X,Z],[[_,_]|T],Answer):-search([X,Z],T,Answer).

intersection([],_,[]).
intersection([[H,O]|T],L2,[Z|Temp]):-
         member([H,_],L2),
         search([H,O],L2,Z),
         intersection(T,L2,Temp).
intersection([H|T],L2,Temp):-
         \+member(H,L2),
          intersection(T,L2,Temp).

When I test it on this : intersection([[1,2],[2,2],[5,5]] , [[1,1],[2,3],[4,5]],A). It gives A = [[1, 1], [2, 2]] , A = [[1, 1]] and A = [[2, 2]] A = [] I only want the first answer, How can I do it? what is wrong with my code?

3
  • Have a look at !. apropos(!).
    – User
    Feb 3, 2014 at 17:07
  • Even better, try once(intersection([[1,2],[2,2],[5,5]] , [[1,1],[2,3],[4,5]],A)).
    – Fred Foo
    Feb 3, 2014 at 17:17
  • @larsmans it works but I don't want this solution :D Feb 3, 2014 at 17:33

1 Answer 1

1

I think that using member/2 followed by a search/3 creates the subset solutions due to backtracking. The search/3 predicate will already provide success or failure depending upon membership by its design. So, if you reswizzle your intersection/3 predicate, you can eliminate the redundancy and enforce the full solution.

You can also eliminate your min/3 predicate noting that SWI Prolog supports a min/2. You would replace min(Y, W, Z) with Z is min(Y, W), but just being aware the assumption is that both Y and W are always instantiated.

search([X,Y], [[X,W]|_], [X,Z]) :- Z is min(Y, W).
search([X,Z], [_|T], Answer) :- search([X,Z], T, Answer).

intersection([], _, []).
intersection([[H,O]|T], L2, R) :-
    (  search([H,O], L2, Z)
    -> R = [Z|Temp]
    ;  R = Temp
    ),
    intersection(T, L2, Temp).

?- intersection([[1,2],[2,2],[5,5]], [[1,1],[2,3],[4,5]], A).
A = [[1, 1], [2, 2]].

?-

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.