list - contar sucesiones sucesivas de número en Prolog
run-length-encoding (5)
¿Por qué está estableciendo una relación entre dos listas con un predicado que tiene 4 argumentos? Tratemos de proceder paso a paso.
Una lista vacía da una lista vacía, un elemento contado se incrementa, de lo contrario, comienza a contar ...
count([],[]).
count([X|T],[[X,C1]|R]) :- count(T,[[X,C]|R]), !, C1 is C+1.
count([X|T],[[X,1]|R]) :- count(T,R).
?- count([1,1,1,2,2,2,3,1,1],R).
R = [[1, 3], [2, 3], [3, 1], [1, 2]].
tan fácil (por supuesto, suponiendo que X = [[1,3,], [2,3], [1,3] [1,2]] es un error tipográfico ...)
Hola, estoy intentando hacer un programa en Prolog que, dada una lista, cuente las ocurrencias de cada elemento sucesivo en la lista de la siguiente manera:
count(1,[1,1,1,2,2,2,3,1,1],0,X)
el resultado sería X=[ [1,3],[2,3],[3,1][1,2] ] aka cada sublista es [element,occurrences]
En mi caso, creo que hay algo mal con el caso base, pero no puedo resolverlo. ¿Me puedes ayudar?
%append an element to a list
append([ ],Y,Y).
append([X|Xs],Ys,[X|Zs]):-append(Xs,Ys,Zs).
%c is the counter beginning with 0
count(_,[],_,[]).
count(X,[X],C,[L]):-count(X,[],C,[L|[X,C]]).
%increase counter
count(X,[X|Tail],C,L):-Z is C+1,count(X,Tail,Z,L).
count(X,[Head|Tail],C,[L]):-append(L,[X,C],NL),count(Head,Tail,1,NL).
Otra solución (cola recursiva) es esta:
run_length_encode( Xs , Ys ) :- % to find the run length encoding of a list ,
rle( Xs , 1 , Ys ) . % - just invoke the helper
rle( [] , _ , [] ) . % the run length encoding of the empty list is the empty list
rle( [A] , N , [X:N] ) . % A list of length 1 terminates the run: move the run length to the result
rle( [A,A|Xs] , N , Ys ) :- % otherwise, if the run is still going
N1 is N+1 , % - increment the count,
rle( [A|Xs] , N1 , Ys ) % - and recurse down
. %
rle( [A,B|Xs] , N , [A:N|Ys] ) :- % otherwise, if the run has ended
A /= B , % - we have a break
rle( [B|Xs] , 1 , Ys ) % - add the completed run length to the result and recurse down
. %
Si saltamos el uso de "es" podemos tener una solución como:
precondition(Clause):-
Clause =.. [_|ARGS],
( maplist(var,ARGS) -> true; Clause ).
count( [], [] ).
count( [X], [(X,1)] ) :- !.
count( [H|Q], [(H,1),(HR,NR)|QR] ) :-
count( Q, [(HR,NR)|QR] ),
H /= HR,
!.
count( [H|Q], [(H,NR)|QR] ) :-
precondition( succ(N,NR) ),
count( Q, [(H,N)|QR] ),
succ(N,NR).
eso permite no solo la consulta habitual:
[debug] ?- count([1,1,1,2,2,2,3,1,1],R).
R = [ (1, 3), (2, 3), (3, 1), (1, 2)].
sino también el reverso:
[debug] ?- count(X, [ (1, 3), (2, 3), (3, 1), (1, 2)] ).
X = [1, 1, 1, 2, 2, 2, 3, 1, 1].
¡Aquí hay otro intento de hacer una codificación de longitud de ejecución, basada en clpfd !
:- use_module(library(clpfd)).
En if_/3 de if_/3 y (=)/3 , definimos list_rle/2 :
list_rle([],[]). list_rle([X|Xs],[N*X|Ps]) :- list_count_prev_runs(Xs,N,X,Ps). list_count_prev_runs(Es,N,X,Ps) :- N #> 0, N #= N0+1, list_count_prev_runs_(Es,N0,X,Ps). list_count_prev_runs_([],0,_,[]). list_count_prev_runs_([E|Es],N,X,Ps0) :- if_(X=E, list_count_prev_runs(Es,N,X,Ps0), (N = 0, Ps0 = [M*E|Ps], list_count_prev_runs(Es,M,E,Ps))).
Consultas de muestra:
codificar / decodificar # 1
?- list_rle([a,a,b,c,c,c,d,e,e],Ys). Ys = [2*a,1*b,3*c,1*d,2*e]. ?- list_rle(Xs,[2*a,1*b,3*c,1*d,2*e]). Xs = [a,a,b,c,c,c,d,e,e] ; false.
codificar / descodificar # 2
?- dif(A,B),dif(B,C),dif(C,D),dif(D,E), list_rle([A,A,B,C,C,C,D,E,E],Ys). Ys = [2*A,1*B,3*C,1*D,2*E], dif(A,B), dif(B,C), dif(C,D), dif(D,E). ?- list_rle(Xs,[2*A,1*B,3*C,1*D,2*E]). Xs = [A,A,B,C,C,C,D,E,E], dif(A,B), dif(B,C), dif(C,D), dif(D,E) ; false.
¿Qué tal algo un poco más general?
?- list_rle([A,B,C,D],Xs). Xs = [4*A ], A=B , B=C , C=D ; Xs = [3*A, 1*D], A=B , B=C , dif(C,D) ; Xs = [2*A, 2*C ], A=B , dif(B,C), C=D ; Xs = [2*A, 1*C,1*D], A=B , dif(B,C), dif(C,D) ; Xs = [1*A,3*B ], dif(A,B), B=C , C=D ; Xs = [1*A,2*B, 1*D], dif(A,B), B=C , dif(C,D) ; Xs = [1*A,1*B,2*C ], dif(A,B), dif(B,C), C=D ; Xs = [1*A,1*B,1*C,1*D], dif(A,B), dif(B,C), dif(C,D).
¡Podemos abordar su problema y preservar la pureza lógica !
A continuación, deje Xs ser [1,1,1,2,2,2,3,1,1] , la lista que utilizó en su pregunta.
Primero , Yss Xs a una lista de listas Yss tal que cada lista Ys en Yss solo contiene elementos iguales tomados de Xs . Hacemos eso usando el meta-predicate splitlistIfAdj/3 en tándem con el predicado de desigualdad reified dif/3 :
?- Xs = [1,1,1,2,2,2,3,1,1], splitlistIfAdj(dif,Xs,Yss).
Xs = [ 1,1,1, 2,2,2, 3, 1,1 ],
Yss = [[1,1,1],[2,2,2],[3],[1,1]].
Segundo , Yss la lista de listas Yss a Zss . Cada elemento en Zss tiene la forma [Element,Amount] . Mirando la respuesta de la consulta anterior, vemos que todo lo que tenemos que hacer es asignar [ 1 , 1 , 1 ] a [ 1 , 3 ] , [ 2 , 2 , 2 ] a [ 2 , 3 ] , [ 3 ] para [ 3 , 1 ] y [ 1 , 1 ] a [ 1 , 2 ] . run_pair/2 hace exactamente eso:
run_pair(Ys,[Element,Amount]) :-
Ys = [Element|_],
length(Ys,Amount).
run_pair/2 para asignar cada elemento de Yss , con la ayuda de meta-predicate maplist/3 :
?- Yss = [[1,1,1],[2,2,2],[3],[1,1]], maplist(run_pair,Yss,Zss). Yss = [[1,1,1],[2,2,2],[3] ,[1,1]], Zss = [[1,3], [2,3], [3,1],[1,2]].
¡Hecho! Es hora de poner todo junto:
count(Xs,Zss) :-
splitlistIfAdj(dif,Xs,Yss),
maplist(run_pair,Yss,Zss).
Veamos si la consulta anterior todavía funciona :)
?- count([1,1,1,2,2,2,3,1,1],Zss).
Zss = [[1,3],[2,3],[3,1],[1,2]]. % succeeds deterministically
Como la implementación de count/2 es monótona , obtenemos respuestas lógicamente sólidas incluso cuando se trabaja con términos no terrestres. ¡Veamos eso en acción!
?- Xs = [A,B,C,D], count(Xs,Zss).
Xs = [D,D,D,D], A=B, B=C , C=D , Zss = [ [D,4]] ;
Xs = [C,C,C,D], A=B, B=C , dif(C,D), Zss = [ [C,3],[D,1]] ;
Xs = [B,B,D,D], A=B, dif(B,C), C=D , Zss = [ [B,2], [D,2]] ;
Xs = [B,B,C,D], A=B, dif(B,C), dif(C,D), Zss = [ [B,2],[C,1],[D,1]] ;
Xs = [A,D,D,D], dif(A,B), B=C , C=D , Zss = [[A,1], [D,3]] ;
Xs = [A,C,C,D], dif(A,B), B=C , dif(C,D), Zss = [[A,1], [C,2],[D,1]] ;
Xs = [A,B,D,D], dif(A,B), dif(B,C), C=D , Zss = [[A,1],[B,1], [D,2]] ;
Xs = [A,B,C,D], dif(A,B), dif(B,C), dif(C,D), Zss = [[A,1],[B,1],[C,1],[D,1]].