Calculul histogramei unei liste in Prolog
<![CDATA[
/*****************************************
* Determinarea numarului de aparitii ale elementelor unei liste
* Paul Mateescu, grupa 309-Informatica, an III-ZI, 2009.
* Facultatea de Matematica si Informatica, Universitatea Spiru Haret Bucuresti.
******************************************
* Problema:
* Dandu-se o lista de numere, sa se furnizeze intr-o alta lista frecventa lor de aparitie:
* Exemplu de utilizare:
* frecv([1, 2, 2, 7, 4, 4, 2, 3, 1, 3, 1, 1, 9, 7, 5], X)
* va genera solutia unica X = [f(1, 4), f(2, 3), f(7, 2), f(4, 2), f(3, 2), f(9, 1), f(5, 1)]
*
*/
trail=4000
domains
item = integer
iteml = item*
integerl = integer*
fr = f(item, integer)
frl = fr*
predicates
run(integer, iteml, frl) % genereaza o lista de nr aleatoare si calculeaza frecventele de aparitie
randomlist(integer, iteml) % genereaza o lista de numere aleatoare in intervalul 0..9
frecv(iteml, frl) % initiaza calculul frecventei, serveste drept interfata cu utilizatorul
frecvh(item, iteml, integer, integer, iteml, iteml, frl) % functie ajutatoare care realizeaza calculul propriu-zis al frecventei
clauses
% Un predicat care genereaza o lista de lungime ceruta, apoi calculeaza frecventa de aparitie a elementelor:
% (i, o, o)
% Notand run(N, L, F), semnificatia argumentelor este:
% N - numarul dorit de elemente al listei
% L - lista de N elemente aleatoare
% F - lista de frecvente de aparitii ale elementelor listei L
run(N, L, F) :-
randomlist(N, L),
frecv(L, F).
/***************************************************************/
% Un predicat care genereaza o lista cu mai multe elemente alese aleatoriu in intervalul 0..9, util pentru testare:
% (i, o)
% Notand randomlist(N, L), semnificatia argumentelor este:
% N - numarul dorit de elemente din lista
% L - Lista cu N elemente
randomlist(0, []).
randomlist(N, [H|T]) :-
N > 0,
N1 = N - 1,
random(9, H),
!,
randomlist(N1,T).
/***************************************************************/
% Predicatul care initiaza calculul frecventei aparitiilor elementelor in cadrul listei:
% (i, o)
% Notand frecv(ITEML, FRL), semnificatia argumentelor este:
% ITEML - lista cu elementele ale caror frecventa dorim sa o calculam
% FRL - lista calculata de frecvente, de forma [f(numar1, frecventa_numar1), f(numar2, frecventa_numar2),…]
% Lista de frecvente ale unei liste vide este lista vida:
frecv([], []).
% Initiaza calculul frecventei de aparitii a primului element de lista, construind
% de la bun inceput primul element al listei de frecvente si facand unificarile corespunzatoare:
frecv([H|T], [f(H, N)|RESTLISTFRECV]) :-
frecvh(H, T, 1, N, LF, LF, RESTLISTFRECV).
/***************************************************************/
% Predicatul ajutator care efectueaza numararea propriu-zisa:
% (i, i, i, o, o, o, o)
% notand frecvh(ELEM, LISTA, APARITII_I, APARITII_TOTALE, ELEM_CURENT_LISTA_FILTRATA, LISTA_FILTRATA,
% REST_LISTA_FRECVENTE), semnificatia argumentelor este:
% ELEM - elementul ale carui aparitii le numaram la pasul curent
% LISTA - portiunea din lista de inspectat ramasa in care numaram aparitiile lui ELEM
% APARITII_I - numarul de aparitii de pana acum ale elementului ELEM
% APARITII_TOTALE - numarul total de aparitii ale elementului ELEM
% ELEM_CURENT_LISTA_FILTRATA - elementul curent al listei filtrate, care se va construi in pasul curent
% LISTA_FILTRATA - intreaga lista filtrata (care nu va mai contine aparitii ale lui ELEM)
% REST_LISTA_FRECVENTE - variabila care se va unifica cu restul listei de frecvente, dupa calculul frecventei lui ELEM
% Elementul curent este gasit in capul listei de inspectat. Incrementam nr. de aparitii, dar
% nu il trecem in lista filtrata:
frecvh(H, [H|T], N, NTOTAL, LFI, LF, RESTLISTFRECV) :-
N1 = N + 1,
!,
frecvh(H, T, N1, NTOTAL, LFI, LF, RESTLISTFRECV).
% Elementul curent nu este gasit in capul listei de inspectat. Nu incrementam nr. de aparitii, dar
% il trecem in lista filtrata:
frecvh(H, [Y|T], N, NTOTAL, [Y|RLFI], LF, RESTLISTFRECV) :-
H <> Y,
!,
frecvh(H, T, N, NTOTAL, RLFI, LF, RESTLISTFRECV).
% Am ajuns la capatul listei de inspectat si lista filtrata este vida.
% Deci am ajuns la finalul algoritmului, unificam numarul total de aparitii al elementului numarat cu numarul curent de aparitii,
% Unificam si restul listei de frecvente cu [], pentru a inchide lista
frecvh(_, [], N, N, [], [], []).
% Am ajuns la capatul listei de inspectat, insa lista filtrata nu este vida.
% Reluam prin initierea detectarii nr. de aparitii al capului listei filtrate (HLF) in restul (coada) listei filtrate, TLF.
% Initiem nr de aparitii cu 1, pentru lua in considerare si aparitia sa initiala din capul listei filtrate.
frecvh(_, [], N, N, [], [HLF|TLF], [f(HLF, NHLF)|REST]) :-
frecvh(HLF, TLF, 1, NHLF, LF, LF, REST).
]]>