Lukas Karmanovas
Lukas Karmanovas

Reputation: 409

Getting successive element that is repeated in a list n times prologue

I am trying to make function that returns element witch is repeated n times in a list. Something like this:

repeat([a,a,c,a,b,b,b,b,a,g],4,E).

And result of this should be E = b. What is the easiest way of doing so? Also those 4 elements have to be successive.

The code to get all elements occurrences count:

precondition(Clause):-
    Clause =.. [_|ARGS],
    ( maplist(var,ARGS) -> true; Clause ).

count( [], [] ).

count( [X], [(X,1)] ) :- !.

count( [H|Q], [(H,1),(HR,NR)|QR] ) :-
    count( Q, [(HR,NR)|QR] ),
    H \= HR,
    !.

count( [H|Q], [(H,NR)|QR] ) :-
    precondition( succ(N,NR) ),
    count( Q, [(H,N)|QR] ),
    succ(N,NR).

Upvotes: 0

Views: 603

Answers (2)

bob_saginowski
bob_saginowski

Reputation: 1429

Maybe a few more test should be done but here is my solution (comparison operators are for integers):

repeat([L], 0, X) :- L \= X.
repeat([L], 1, X) :- L == X.
repeat([X|T], C, X) :- C1 is C - 1, repeat(T, C1, X).
repeat([_|T], C, X) :- repeat(T, C, X).

EDIT I noticed that the solution provided for your example will also return E=a but it shouldn't. So here is the new approach: generate all sublists from the given, check if generated lists contain the same element and then check if the length of those lists is the second argument C

sublist([],[]).
sublist([H|T], [H|Q]) :- sublist(T,Q).
sublist([_|T], Q) :- sublist(T,Q).

sameelements([X], X).
sameelements([X|T], X) :- sameelements(T, X).

len([], 0).
len([_|T], C) :- len(T, C1), C is C1 + 1.

repeat(L, C, X) :- sublist(L, SL), len(SL, C), sameelements(SL, X).

Upvotes: 2

user1812457
user1812457

Reputation:

Once you have a list like you do, you can just use member/2:

?- R = [(a, 2), (c, 1), (a, 1), (b, 4), (a, 1), (g, 1)], 
   member((Element, 4), R).
R = [(a, 2),  (c, 1),  (a, 1),  (b, 4),  (a, 1),  (g, 1)],
Element = b ;
false.

It would be a bit more Prolog-like if you made a list like [a-2, c-1, a-1, ...], then used member(Element-4, R) instead. A term like (a, b, ...) is not a tuple like in other languages, and a-b is commonly used as a pair.

And here is how I would do it, if I would use the libraries available with SWI-Prolog:

L = [a,a,c,a,b,b,b,b,a,g], N = 4,
    pairs_keys_values(Ps, L, L),
    group_pairs_by_key(Ps, G),
    include([X-Xs]>>length(Xs, N), G, R),
    member(Element-_, R).
% some results you don't need
Element = b.

The line with include is not strictly necessary, but it avoids unnecessary choice points.

Upvotes: 3

Related Questions