How can i find pairs in a list, Prolog?

Question

I have a problem, I have a list with numeric elements such as in the example. I´d like to find all pairs, and count it. (Every Element can only be one part of one pair)

?- num_pairs([4,1,1,1,4],N).
N=1;

Can anyone help me to solve this problem??

Sergey Kalinichenko Sergey Kalinichenko · Accepted Answer · 2012-12-13T21:23:09

You need several things to make it work:

An ability to count the number an item is repeated in a list
An ability to remove all elements matching a value from the list
An ability to conditionally increment a number

Here is how you can count:

count([], _, 0).
count([H|T], H, R) :- count(T, H, RT), R is RT + 1.
count([H|T], X, R) :- H \= X, count(T, X, R).

Deletion can be done with SWI's delete/3 predicate; this is a built predicate.

Adding one conditionally requires two rules - one when the count equals one, and another one for when the count does not equal one.

add_if_count_is_one(H, T, RT, R) :- count(T, H, 1), R is RT + 1.
add_if_count_is_one(H, T, R, R) :- count(T, H, X), X \= 1.

Finally, counting pairs could look like this:

num_pairs([], 0).
num_pairs([H|T], R) :- delete(T, H, TT),
                       num_pairs(TT, RT),
                       add_if_count_is_one(H, T, RT, R).

An empty list has no pairs; when an item is counted as part of a pair, its copies are removed from the rest of the list.

Here is this running program on ideone.

How can i find pairs in a list, Prolog?

1 Answers