CODEWITHSUNDEEP
prolog
JaAnTr
JaAnTr

Reputation: 906

Removing list within lists based on nth element

I've got a list of lists, for example:

[[1, 2, 3, 2], [1, 3, 4, 3], [1, 4, 5, 4], [2, 3, 5, 6], [1, 5, 6, 5], 
[2, 4, 6, 8], [1, 6, 7, 6], [2, 5, 7, 10], [3, 4, 7, 12], [2, 6, 8, 12]]

I'd like to get the last element of and check to see if is the same as the 4th element of any of the other lists. If it is the same then leave the list alone, but if it is unique then remove the list. So in the example above I would be left with:

[[3, 4, 7, 12], [2, 6, 8, 12]]

Essentially I want to be remove all the lists where the last element is unique. I've written a predicate to get the nth element:

my_membership(X, [X|_]).                           
my_membership(X, [_|Tail]) :-  
  my_membership(X, Tail).

where:

my_membership([_,_,_,Fourth],[[3, 4, 7, 12], [2, 6, 8, 12]]).

gives:

Fourth = 12 
Fourth = 12

Upvotes: 1

Views: 151

Answers (2)

lurker
lurker

Reputation: 58244

Here's a different twist on a potential solution. It uses an accumulator to collect members that we've seen already and checks along the way. The result saves those that have either been seen or are currently in the tail. It requires the use of the built-in, memberchk/2.

my_membership(L, R) :-
    my_membership(L, [], R).

my_membership([], _, []).
my_membership([X|T], Acc, R) :-
    X = [_,_,_,D],
    (   memberchk([_,_,_,D], Acc)
    ->  R = [X|T1],
        Acc1 = Acc
    ;   memberchk([_,_,_,D], T)
    ->  R = [X|T1],
        Acc1 = [X|Acc]
    ;   R = T1,
        Acc1 = Acc
    ),
    my_membership(T, Acc1, T1).

| ?- my_membership([[1, 2, 3, 2], [1, 3, 4, 3], [1, 4, 5, 4], [2, 3, 5, 6], [1, 5, 6, 5],
[2, 4, 6, 8], [1, 6, 7, 6], [2, 5, 7, 10], [3, 4, 7, 12], [2, 6, 8, 12]], L).

L = [[2,3,5,6],[1,6,7,6],[3,4,7,12],[2,6,8,12]]

yes

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726499

Start by building two basic predicates:

last([X], X).
last([_|T], X) :- last(T, X).

forth([_,_,_,F|_], F).

The first predicate extracts the last element of a list; the second predicate extracts the forth element of a list.

Now you can make a predicate that counts how many tomes an element X appears in forth place in any of the lists of a list of lists. Below, H in [H|T] is a list:

matching_forth([], _, 0).
matching_forth([H|T], X, R) :- forth(H, X), matching_forth(T, X, RR), R is RR + 1.
matching_forth([_|T], X, R) :- matching_forth(T, X, R).

With these predicates in place you can build a predicate for checking your condition. It will have three clauses - for a situation when the list is empty, for when the head list has a matching forth element in another list, and for situations when it doesn't:

my_membership([], [], _).
my_membership([H|T], [H|R], A) :-
   last(H, X), matching_forth(A, X, C), C > 1, my_membership(T, R, A).
my_membership([_|T], R, A) :- my_membership(T, R, A).

The first and last clauses are self-explanatory. The middle clause extracts the last element from the head list, counts how many times it matches the forth element in the original list of lists (A stands for "all"), and adds H to the result when there is a match. Adding happens through unification with the head of the result list.

Finally, you need a my_membership/2 predicate to start off the recursive chain that passes along the original list of lists:

my_membership(L, R) :-  my_membership(L, R, L).

Demo.

Upvotes: 1

Related Questions