prolog Searching the Lists

Question

I am trying to compare the lists. Given function(List1,List2) and List1 has length N and List 2 has length M and N>M.

I want to check if any permutation of List2 happens to be the first M characters of List1.

eg,

predicate([a,c,b,d,e],[a,b,c,d]).

should be true and

predicate([a,c,b,e,d],[a,b,c,d]).

should be false.

Thank you.

Answer 1

Using the permutation/2 and prefix/2 predicates you could write something such as :

has_prefix_perm(List1, List2) :-
    permutation(List2, Permutation),
    prefix(Permutation, List1),
    !.

As a side note and to quote swi-prolog manual :

Note that a list of length N has N! permutations and unbounded permutation generation becomes prohibitively expensive, even for rather short lists (10! = 3,628,800).

So I'd take care not to call has_prefix_perm/2 with a too lengthy second list, especially if it happens not to be a prefix modulo permutation, since all the cases will be tested.

Another way would be to test if List1 items are members of List2 until List2 is empty, that way you know that a permutation exists :

has_prefix_perm(_, []) :- !.
has_prefix_perm([Head1|List1], List2) :-
    once(select(Head1, List2, Rest)),
    has_prefix_perm(List1, Rest).

Written like that, I wouldn't use it on non ground lists, but seeing your OP I didn't search further...

Another way would be to check if List1 reduced to the length of List2 is a permutation of List2 :

has_prefix_perm(List1, List2) :-
    length(List2, L),
    length(LittleL1, L),
    append(LittleL1, _, List1),
    permutation(LittleL1, List2),
    !.

Another way would be to... I guess there are lots of ways to do that, just pick one that isn't horrible complexity wise and fits your style ! :)

I'd go with the last one personally.

Answer 2

As often when describing relations between lists, DCGs are convenient in this case:

perm_prefix(Ls1, Ls2) :- phrase(perm(Ls2), Ls1, _).

perm([])  --> [].
perm(Ls0) --> [L], { select(L, Ls0, Ls1) }, perm(Ls1).

Sample cases:

?- perm_prefix([a,c,b,d,e],[a,b,c,d]).
true

?- perm_prefix([a,c,b,e,d],[a,b,c,d]).
false.

Answer 3

Here is another DCG solution.

perm(Xs,Ys) :- phrase(perm(Xs),[],Ys).

perm([])-->[].
perm([X|Xs])-->perm(Xs),ins(X).

ins(X),[X]-->[].
ins(X),[Y]-->[Y],ins(X).

Attribution: Moments of Prolog, exhibit 0