Prolog Search Lists

Question

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

I want to check if any permutation of List2 is the first M-characters of List1.

eg,

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

must be true and

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

must be false.

Thanks.

Answer 1

Using the permutation/2 and prefix/2 predicates, you can write something like:

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

As a side note and quote from the swi-proog manual :

Note that a list of length N has N! permutations and unlimited generation of permutations become excessively expensive even for fairly short lists (10! = 3,628,800).

Therefore, I would not call has_prefix_perm/2 too long a second list, especially if it is not a prefix modulo permutation, since all cases will be tested.

Another way is to check if List1 elements are members of List2 until List2 is empty, so you know that there is a permutation:

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

Written in this way, I would not use it on non-natural lists, but when I saw your OP, I was no longer looking ...

Another way is to check if List1 is reduced to the length of List2, permuting List2:

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

Another way would be ... I suppose there are many ways to do this, just choose one that is not terrible complexity and fits your style! :)

I would go with the latter personally.

Answer 2

How often when describing the relationship 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). 

Examples of 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: Prologue moments, exhibit 0