Menu
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.
246
To check if a variable is bound to a list, you can use is_list/1 .
item_list(Xs) :- findall(X, item(X), Xs). is_member(X) :- item_list(Xs), member(X, Xs). although … if there is no need to actually grab the whole list, then this can be simplified to a simple predicate lookup: is_member(X) :- item(X).
Try this: same(X, X). same([A| B], [C| D]):- A=C, same(B,D). it'll return true if they are the same.
In Prolog list elements are enclosed by brackets and separated by commas. Another way to represent a list is to use the head/tail notation [H|T]. Here the head of the list, H, is separated from the tail of the list, T, by a vertical bar.
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.
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.
27
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
