CODEWITHSUNDEEP
listprologsublist
arkham knight
arkham knight

Reputation: 383

Prolog - first list is sublist of second list while maintaining order?

I want to check if elements of list L1 occur consecutively, and in the same order, in list L2.

For example - check([b,c],[a,b,c,d]) must return true while check([b,d],[a,b,c,d]) must return false

I looked at similar posts Prolog - first list is sublist of second list? and also tried out similar solutions but whenever i try to check if elements are present, i am unable to check if ordering is consecutive

check( [], _ ).
check( [X|XS], [X|XSS] ) :- sublist( XS, XSS ).
check( [X|XS], [_|XSS] ) :- sublist( [X|XS], XSS ).

and if i try to check if ordering is correct then my code is breaking.

check( [], _ ).
check( [X|XS], [X|XSS] ) :- sublist( XS, XSS ).

Upvotes: 3

Views: 1667

Answers (3)

Paulo Moura
Paulo Moura

Reputation: 18663

An alternative solution using the de facto standard definition of the append/3 predicate:

check(SubList, List) :-
    append(Prefix, _, List),
    append(_, SubList, Prefix).

Sample calls:

| ?- check([b,d],[a,b,c,d]).

no

| ?- check([b,c],[a,b,c,d]).

true ? ;
no

| ?- check([b,c],[a,b,c,d,b,c,f]).

true ? ;
true ? ;
no

We can also use this definition to generate sublist-list pairs:

| ?- check(SubList, List).

SubList = [] ? ;

List = [A|_]
SubList = [A] ? ;

List = [_|_]
SubList = [] ? ;

List = [A,B|_]
SubList = [A,B] ? ;

List = [_,A|_]
SubList = [A] ? ;

List = [_,_|_]
SubList = [] ? ;

List = [A,B,C|_]
SubList = [A,B,C] ? ;

List = [_,A,B|_]
SubList = [A,B] ? ;

...

This problem also gives you the opportunity to learn about termination properties of predicates. As an experiment, exchange the order of the append/3 calls and then check what happens on backtracking for e.g. the two first sample calls.

Upvotes: 3

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476554

We can make use of append/2 [swi-doc] to write this with a one-liner:

subsequence(X, Y) :-
    append([_,X,_], Y).

or we can implement a subsequence/4 that will unify two variables Prefix and Suffix with the list before and after the subsequence:

subsequence(X, Y, Prefix, Suffix) :-
    append([Prefix,X,Suffix], Y).

Here we thus have two don't care variables that will collect the prefix and suffix before and after the subsequence.

Upvotes: 3

Daniel Lyons
Daniel Lyons

Reputation: 22803

Interesting problem! I'm surprised at how much code it took, so there may be a better solution than this.

First we need a helper to insist that a list is a prefix of another list. The base case is that we ran out of a prefix list; the inductive case is that the current items match and the remainder of both lists is a prefix match.

prefix([X|Xs], [X|Ys]) :- prefix(Xs, Ys).
prefix([], _).

Now finding a consecutive sublist amounts to searching down a list for prefix matches. If the current items match, then having a prefix is a match:

consecutive_sublist([X|Xs], [X|Ys]) :- prefix(Xs, Ys).

Otherwise, we just discard this element of the search target and try again on the sublist:

consecutive_sublist(Prefix, [_|Ys]) :- consecutive_sublist(Prefix, Ys).

Upvotes: 5

Related Questions