CODEWITHSUNDEEP
prolog
Diego Jimeno
Diego Jimeno

Reputation: 312

Counting duplicate elements in prolog

i'm having problems with this subject in Prolog. The thing is that I want to count the number of repeated elements appearing in a list, and I also want to fill, in another list with 1, for each appearance of duplicated elements and a 0 if is not duplicated, e.g.

I have a list like this: [420,325,420,582,135,430,582], and the result should be [1,0,1,1,0,0,1].

I've tried some code snippets and it's driving me nuts.

The last code i've tried is: 

count_duplicates([],[]).
count_duplicates([Head|Tail],[1|LS]):-
    member(Head,Tail),
    count_duplicates([Tail|Head],LS).

count_duplicates([Head|Tail],[0|LS]):-
    \+ member(Head,Tail),
    count_duplicates([Tail|Head],LS).

this predicate receive a list and have to generate the result list

Thanks in advance

Upvotes: 0

Views: 3088

Answers (2)

joel76
joel76

Reputation: 5645

You can try this :

count_duplicate(In, Out) :-
    maplist(test(In), In, Out).


test(Src, Elem, 1) :-
    select(Elem, Src, Result),
    member(Elem, Result).

test(_Src, _Elem, 0).

EDIT Without maplist, you can do

count_duplicate(In, Out) :-
    test(In, In, Out).

test(_, [], []).

test(In, [Elem | T], [R0 | R]) :-
    select(Elem, In, Rest),
    (   member(Elem, Rest) -> R0 = 1; R0 = 0),
    test(In, T, R).

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

I would rewrite using some of list processing builtins available:

count_duplicates(L, R) :-
    maplist(check(L), L, R).

check(L, E, C) :-
    aggregate(count, member(E, L), Occurs),
    ( Occurs > 1 -> C = 1 ; C = 0 ).

with that

?- count_duplicates([420,325,420,582,135,430,582],L).
L = [1, 0, 1, 1, 0, 0, 1].

About your code, I think it's simple to get termination:

count_duplicates([],[]).
count_duplicates([Head|Tail],[1|LS]):-
    member(Head,Tail),
    count_duplicates(Tail,LS).
count_duplicates([Head|Tail],[0|LS]):-
    \+ member(Head,Tail),
    count_duplicates(Tail,LS).

Note I corrected the recursive calls, and consider that could be done in a slightly more efficient way (both source and runtime) using the if .. then .. else .. construct.

count_duplicates([],[]).
count_duplicates([Head|Tail],[R|LS]):-
    ( member(Head,Tail) -> R = 1 ; R = 0 ),
    count_duplicates(Tail,LS).

it's cleaner, isn't it? member/2 it's called just once, that's a big gain, and consider using memberchk/2 instead of member/2.

But that code fails to tag as multiple the last occurrence.

Upvotes: 0

Related Questions