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.

Cyder

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.

Ani

I wish I had enough points to vote you up but Thank you very much Sir!! – Cyder

@salva about your edit, I used append/2 in a correct way, no need to use append/3 ! :p – Ani

Please look at the solution of @mat! Efficient, and no cut! – Covered

@Covered : well mat's solution and the second one proposed there are kinda the same ! – Ani

@Mog. They are not the same. has_prefix_perm([a,b],[X,Y]). finds only one solution. – Covered

@Covered : Well in my mind the kinda accounted for the once/1... that's the only difference. – Ani

@Mog : has_prefix_perm([a,b,c],[X,a,c]). fails when it should succeed with X = b – Covered

@Mog : My point here is to show you that these !s and once/1 simply ruin the semantics. – Covered

@Covered : that's why I said I wouldn't use it with unbound vars. Still this predicate and mat's work the same way and are alike. If you remove the cut and once you obtain the exact same thing, it's just a matter of what you want the predicate to do, not of how it works or style. :( – Ani

But I agree that the cut and once are not necessary at all and more destructive than anything else. – Ani

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.

Madelenemadelin

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

Covered