new kid have question, show number by frequency
Author Message
new kid have question, show number by frequency

I want show groups of number sorted by frequency.
ex. my input is 8 3 2 1 8 5 1
want output to be
3 occurs 1
2 occurs 1
5 occurs 1
8 occurs 2
1 occurs 2

can we do this problem by by PROLOG?

if we can, how can we do that.

Thank you,
hope to hear from you guys soon!

Wed, 24 Sep 1997 03:00:00 GMT
new kid have question, show number by frequency

Quote:

> I want show groups of number sorted by frequency.
> ex. my input is 8 3 2 1 8 5 1
> want output to be
> 3 occurs 1
> 2 occurs 1
> 5 occurs 1
> 8 occurs 2
> 1 occurs 2

> can we do this problem by by PROLOG?

> if we can, how can we do that.

>                                    Thank you,
> hope to hear from you guys soon!

Here is the kernel for a solution. If you use LPA Prolog
you can use it immediately, otherwise you have to do some work
on the sorting of the elements. Furthermore the I/O is left
up to you.

Bye,bye,
Henk

/*
Example calls:

?-sorted_freq_table([8, 3, 2, 1, 8, 5, 1], Table).
No.1 : Table = [2-1, 3-1, 5-1, 1-2, 8-2]

?-sorted_freq_table([1], Table).
No.1 : Table = [1-1]

*/
%
% sorted_freq_table(List_of_scores,List_of_sorted_Score_Freq_pairs)
%
sorted_freq_table([],[]):- !.         % Don't fail if no scores.

sorted_freq_table(List,Sorted_on_freq):-
sort(List,Sorted,[]),                % The empty list prevents the removing
% of double elements (LPA Prolog)
count(Sorted,FreqTable),             % Creates a list of score-freq elements.
sort(FreqTable,Sorted_on_freq,[3]).  % The [3] will make sort/3 use freq in
% the list of the score-freq elements
% as the key (LPA).

%
% count/2: counts the number of times each score occurs and puts the
%          the result for each score in the form of a Score-Freq term
%          in the frequency list
%
count([Score|Scores],Table):-
count(Scores, Score-1,Table).  % Calls the work horse count/3
% setting the 1st score's freq on 1

%
% count/3
%
count([],Score-Freq,[Score-Freq]):- !.         % No more scores.
count([Score|Scores], Score-Freq,Table):- !,   % Same as previous score
Freq_nxt is Freq+1,                           % -> Add 1 to frequency
count(Scores, Score-Freq_nxt,Table).          %    Move to next score
count([NewScore|Scores],Score-Freq,[Score - Freq|Table]):-
/* NewScore != Score */                       % New score:
count(Scores, NewScore-1,Table).              %  Add Score-Freq to result and

Fri, 26 Sep 1997 03:00:00 GMT
new kid have question, show number by frequency
% The following is another solution to the problem of printing
% a frequency table, sorted on frequency. In this solution the
% list of scores is walked through only once, without being sorted
% beforehand, like in my previous solution. For each score a
% counter is updated using retract and/or assert. Somebody will
% probably tell us when to use which technique (if he hasn't done
% This solution includes a printing predicate.
%
% Example call:
%
/*
?-print_freq_table([1, 2, 1, 1, 1, 1, 2, 1, 11, 2, 1, 1, 1, 1, 4, 111, 22, 33, 111, 8], 3, 2).
11 occurs  1 time.
4 occurs  1 time.
22 occurs  1 time.
33 occurs  1 time.
8 occurs  1 time.
111 occurs  2 times.
2 occurs  3 times.
1 occurs 10 times.
No.1 : yes
No more solutions

% The freq/2 facts asserted for this list of scores are
% shown by the following:
:-listing(freq).

% freq/2
freq(11, 1).
freq(2, 3).
freq(1, 10).
freq(4, 1).
freq(22, 1).
freq(33, 1).
freq(111, 2).
freq(8, 1).
*/
:-dynamic freq/2.

%
% print_freq_table(List_of_scores,FieldWidth_for_Scores,FieldWidth_for_Freqs)
%
print_freq_table([],_,_):-!,
write('No Scores!'),
nl.
print_freq_table(List,SW,FW):-
init_freqs,
findall(Score-Freq,freq(Score,Freq),Table),
sort(Table,Sorted_Table,[3]),  %  in LPA [3] causes SortKey=Freq
forall(member(Score-Freq,Sorted_Table),write_line(Score-Freq,SW,FW)).

init_freqs:- abolish(freq/2).

FNew is F+1,
assert(freq(Score,FNew)).
assert(freq(Score,1)).     % First time.

write_line(Score-Freq,SW,FW):-
write_ra(Score,SW),         % write right aligned in field SW wide.
write(' occurs '),
write_ra(Freq,FW),          % write right aligned in field FW wide.
(Freq>1->write(' times.');
write(' time.')),
nl.

write_ra(X,LengField):-
name(X,Chars),
length(Chars,LengX),
NrOfSpaces is LengField - LengX,
(NrOfSpaces > 0 -> write_spaces(NrOfSpaces)
;  true),
write(X).

write_spaces(0):-!.
write_spaces(N):-
put(32),
N_1 is N-1,
write_spaces(N_1).

Fri, 26 Sep 1997 03:00:00 GMT
new kid have question, show number by frequency
/*
Here is a cleaner way to compute the number of occurences of values in a list.
(You don't need assert, retract, forall, sort, findall - recursion does it).

Example - printing routines are omitted
[eclipse]: score([1, 2, 1, 1, 1, 1, 2, 1, 11, 2, 1, 1, 1, 1, 4, 111, 22, 33, 111, 8],S).

S = [1 - 10, 2 - 3, 11 - 1, 4 - 1, 111 - 2, 22 - 1, 33 - 1, 8 - 1]
*/

score(List,Scores):- score(List,[],Scores).

score([],S,S).
score([N|L],S1,S3):-
update_score(N,S1,S2),
score(L,S2,S3).

update_score(N,[],[N-1]).
update_score(N,[N-F|S],[N-F1|S]):- F1 is F+1.
update_score(N,[M-F|S],[M-F|S1]):- N\==M, update_score(N,S,S1).

Sat, 27 Sep 1997 03:00:00 GMT
new kid have question, show number by frequency

Quote:
Kritchai Kuntakom <kkuntako> writes:
>I want show groups of number sorted by frequency.
>ex. my input is 8 3 2 1 8 5 1
>want output to be
>3 occurs 1
>2 occurs 1
>5 occurs 1
>8 occurs 2
>1 occurs 2
>can we do this problem by by PROLOG?

Of course.  Let me give you a hint.  Suppose I had a file with one
number per line.  In UNIX, I could do

sort -n <TheFile | uniq -c

and I'd get output like
1 2
2 1
3 1
5 1
8 2

To finish the hint:  Prolog has a built-in predicate called keysort/2.
That gives you the 'sort' bit; all you have to figure out how is the
'uniq' bit.  If you can't figure it out, ask again.
--
"The complex-type shall be a simple-type."  ISO 10206:1991 (Extended Pascal)
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Sun, 28 Sep 1997 03:00:00 GMT
new kid have question, show number by frequency
Quote:

> /*
> Here is a cleaner way to compute the number of occurences of values in a list.
> (You don't need assert, retract, forall, sort, findall - recursion does it).

> Example - printing routines are omitted
> [eclipse]: score([1, 2, 1, 1, 1, 1, 2, 1, 11, 2, 1, 1, 1, 1, 4, 111, 22, 33, 111, 8],S).

> S = [1 - 10, 2 - 3, 11 - 1, 4 - 1, 111 - 2, 22 - 1, 33 - 1, 8 - 1]
> */

> score(List,Scores):- score(List,[],Scores).

> score([],S,S).
> score([N|L],S1,S3):-
>    update_score(N,S1,S2),
>    score(L,S2,S3).

>    update_score(N,[],[N-1]).
>    update_score(N,[N-F|S],[N-F1|S]):- F1 is F+1.

Quote:
>    update_score(N,[M-F|S],[M-F|S1]):- N\==M, update_score(N,S,S1).

Nice, Tom!

Maybe update_score can be speeded up if we use a sorted list of
Score-Frequency pairs.
(We get a better printable result anyway. BTW, the original
posted problem still requires sort because he wanted
the result sorted on frequency).

See the added, starred clause above. (4th line could be changed too).

For example:
?-score([1,2,1,1,1,1,2,1,11,2,1,1,1,1,4,111,22,33,111,8], S)
No.1 : S = [1-10, 2-3, 4-1, 8-1, 11-1, 22-1, 33-1, 111-2]
No more solutions

Or the more verbose version using compare/3 below:

frequencies(Scores,Score_Freqs):- frequencies(Scores,[],Score_Freqs).

frequencies([],Score_Freqs,Score_Freqs).
frequencies([Score|Scores],Score_Freqs1,Score_Freqs3):-
update_freq(Score,Score_Freqs1,Score_Freqs2),
frequencies(Scores,Score_Freqs2,Score_Freqs3).

update_freq(Score,[],[Score-1]):-!.
update_freq(Score,[S-F|SFs],Score_Freqs):-
compare(R,Score,S),
update_freq_1(R,Score,[S-F|SFs],Score_Freqs).

update_freq_1(<,Score,[S-F|SFs],[Score-1,S-F|SFs]):-!. % Insert Score
update_freq_1(=,Score,[S-F|SFs],[S-F1|SFs]):-!,
F1 is F+1.                                            % Increase Score's freq.
update_freq_1(>,Score,[S-F|SFs],[S-F|SFs1]):-
update_freq(Score,SFs,SFs1).                          % Try next S-F

/*
?-frequencies([1,2,1,1,1,1,2,1,11,2,1,1,1,1,4,111,22,33,111,8],S).
No.1 : S = [1-10,2-3,4-1,8-1,11-1,22-1,33-1,111-2]
No more solutions
*/

Sat, 04 Oct 1997 03:00:00 GMT

 Page 1 of 1 [ 9 post ]

Relevant Pages