I'm trying to work on an assignment, however am really stuck on this section. What I need to do is write a predicate called matching with three parameters, all lists. The third list must contain the index of the positions in which the first two lists contain the same value. I really don't know where to start on this so any help would be much appreciated!
2
votes
2 Answers
2
votes
The third list must contain the index of the positions in which the first two lists contain the same value.
First important:
The third list must contain the index of the positions in which the first two lists contain the same value.
Use unification. As predicate:
same_value(X, X).
The third list must contain the index of the positions in which the first two lists contain the same value.
lists_same_value([X|_], [Y|_]) :- same_value(X, Y). % succeed
lists_same_value([_|Xs], [_|Ys]) :- % skip head
lists_same_value(Xs, Ys). % recursive definition
Simplify and unify in head:
lists_same_value([X|_], [X|_]). % succeed
lists_same_value([_|Xs], [_|Ys]) :- % skip head element
lists_same_value(Xs, Ys). % recursive definition
The third list must contain the index of the positions in which the first two lists contain the same value.
Add accumulator for current index, succeed when heads are same element, and look in rest of list.
lists_same_value_index([X|_], [X|_], N, N). % succeed
lists_same_value_index([_|Xs], [_|Ys], N0, N) :- % skip head element
succ(N0, N1), % next index
lists_same_value_index(Xs, Ys, N1, N). % recursive definition
Instantiate accumulator:
lists_same_value_index(Xs, Ys, N) :-
lists_same_value_index(Xs, Ys, 0, N).
Use it with bagof to find all solutions:
?- bagof(N, lists_same_value_index([a,b,c,a,c,d,c], [a,c,c,a,d,d,c], N), Ns).
Ns = [0, 2, 3, 5, 6].
and no this is not the same as the solution with the two nth0 of course, see:
?- numlist(1, 100, L), time( bagof(N, lists_same_value_index(L, L, N), Ns) ).
% 314 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1785481 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].
?- numlist(1, 100000, L), time( bagof(N, lists_same_value_index(L, L, N), Ns) ).
% 300,014 inferences, 0.052 CPU in 0.052 seconds (100% CPU, 5765387 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].
and then with nth0:
?- numlist(1, 100, L), time( findall(N, ( nth0(N, L, E), nth0(N, L, E) ), Ns) ).
% 2,181 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 3329847 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].
?- numlist(1, 100000, L), time( findall(N, ( nth0(N, L, E), nth0(N, L, E) ), Ns) ).
% 1,667,166,681 inferences, 151.139 CPU in 151.244 seconds (100% CPU, 11030703 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Ns = [0, 1, 2, 3, 4, 5, 6, 7, 8|...].
1
votes
As @Capellic suggested you can use findall/3 and nth1/3 predicates:
common_elemnts_pos(L1,L2,Pos):-
findall(X, (nth0(X,L1,Elem), nth0(X, L2, Elem)) , Pos).
The above simply says that find all positions X that the element in L1 is Elem and element in L2 is Elem, so the have same element.
Example:
?- common_elemnts_pos([1,3,4,5,7,9],[1,2,4,5,8,9],Pos).
Pos = [0, 2, 3, 5].
It is also easy to do a pure recursive solution like:
common_elemnts_pos(L1,L2,Pos):- common_elemnts_pos(L1,L2,Pos,0).
common_elemnts_pos([],_,[],_).
common_elemnts_pos(_,[],[],_).
common_elemnts_pos([H|T],[H|T1],[CurrentPos|T2],CurrentPos):-
N_CurrentPos is CurrentPos+1,
common_elemnts_pos(T,T1,T2,N_CurrentPos).
common_elemnts_pos([H|T],[H1|T1],T2,CurrentPos):-
dif(H,H1), N_CurrentPos is CurrentPos+1,
common_elemnts_pos(T,T1,T2,N_CurrentPos).
Example:
?- common_elemnts_pos([1,3,4,5,7,9],[1,2,4,5,8,9],Pos).
Pos = [0, 2, 3, 5] ;
Pos = [0, 2, 3, 5] ;
false.
?- common_elemnts_pos([1,3,4,5,7,9],[1,2,4,5,8,9],Pos).
Pos = [0, 2, 3, 5] ;
false.
In first test above there are two same solutions because both base cases are valid. If you want only one you could replace:
common_elemnts_pos([],_,[],_).
common_elemnts_pos(_,[],[],_).
with base case:
common_elemnts_pos([],[_|_],[],_).
common_elemnts_pos(_,[],[],_).
