CODEWITHSUNDEEP
prolog
Monolith
Monolith

Reputation: 39

Prolog checking if 2 lists have same number of elements

I am trying to figure out how to do this little thing. I have 2 lists for example [1,1,2,3,4] and [2,1,4,3,1], I need to confirm if all elements from list 1 are included in list 2, soo if i give the above lists as input this should be true, but if its like this [1,1,2,3,4] and [2,1,4,3,1,1] (three 1's) it should give false, this has to be done without using sort function.

Upvotes: 1

Views: 248

Answers (1)

Duda
Duda

Reputation: 3746

I assume you know how to write a list as head and tail ([H|L]).
So you could use the predicate member/2 to ask for every element from the first list to be in the second list as well, but this would not solve the issue of duplicates. Using the predicate length/2 will not help in this case. So you need something that retracts one matching element from a list. You can either write your own find-and-remove-predicate or use the predicate append/3 to do so. append/3 is thought to append 2 lists to form a third one, but it can also be used to divide one list into two. If you state that your element as the head element of the second divided list you basically get a 'remove element' functionality. Once you've got the 2 divided lists, combine them into a new list and call the predicate again, but this time without the head element from list one and with the reappended-list. So in each step you remove one element from each list until you finally hit two empty lists (permut([],[]).). If something other than this two cases should appear, then the two lists are not permuations of each other and the predicate fails.

Since there is no use in backtracking other positions I inserted a cut (!) after successfully finding an element in the second list. The predicate works without the cut as well.

permut([],[]).
permut([H|T], Compare):-
    append(C1, [H|C2], Compare),
    !,
    append(C1, C2, Cnext),
    permut(T, Cnext).

gives the output

?- permut([1,2,3,4,5],[5,4,3,2,1]).
true.

?- permut([1,2,3,4,5],[5,4,3,2,1,1]).
false.

?- permut([1,2,3,4,5,6],[5,4,3,2,1]).
false.

Upvotes: 1

Related Questions