How can I know how many different integers are in a list ?
Author Message How can I know how many different integers are in a list ?

If I use SWI-prolog, I can know how many different integers are
in a list (ie. remove the doubles) by using list_to_set + length
But how can I do it without list_to_set. I use GNU-prolog and use
sort + length (because 'sort' removes doubles), but is it the most
elegant way, since I don't need at all to sort the elements (just
know how many different values are in the list). I never like the idea
of doing more than what I need. What would you do with GNU-prolog ?

Fri, 04 Jun 2004 22:51:57 GMT  How can I know how many different integers are in a list ?

Quote:

> If I use SWI-prolog, I can know how many different integers are
> in a list (ie. remove the doubles) by using list_to_set + length
> But how can I do it without list_to_set. I use GNU-prolog and use
> sort + length (because 'sort' removes doubles), but is it the most
> elegant way, since I don't need at all to sort the elements (just
> know how many different values are in the list). I never like the idea
> of doing more than what I need. What would you do with GNU-prolog ?

1. list_to_set in SWI prolog is itself implemented in Prolog, so you
can simply look at the definition and use it in GNU-prolog.

\$list_to_set([], []).
\$list_to_set([H|T], R) :-
memberchk(H, T), !,
\$list_to_set(T, R).
\$list_to_set([H|T], [H|R]) :-
\$list_to_set(T, R).

2. however, if GNU-prolog has a decent implementation of sort, then
that's probably going to be much more efficient. Sorting is n log(n)
whereas the definition above is n^2.

Gj

--
Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord

Mon, 07 Jun 2004 15:26:47 GMT  How can I know how many different integers are in a list ?

Quote:

> 2. however, if GNU-prolog has a decent implementation of sort, then
> that's probably going to be much more efficient. Sorting is n log(n)
> whereas the definition above is n^2.

GNU-Prolog as a decent implementation of sort/2, not the fastest one, but
definitely decent.

Cheers

Bart Demoen

Mon, 07 Jun 2004 17:46:40 GMT  How can I know how many different integers are in a list ?

Quote:
> 2. however, if GNU-prolog has a decent implementation of sort, then
> that's probably going to be much more efficient. Sorting is n log(n)
> whereas the definition above is n^2.

If the integers are taken from the range [1..k] you could use counting
sort, which runs in time O(k+n) using arrays.

- martin

Sat, 12 Jun 2004 15:46:16 GMT  How can I know how many different integers are in a list ?

Quote:

> If the integers are taken from the range [1..k] you could use counting
> sort, which runs in time O(k+n) using arrays.

If your Prolog system has something resembling an array... :-)
--

http://www.bawue.de/~jjk/          fax:+49-7031-464-7351
PGP:       06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]

Fri, 25 Jun 2004 22:01:21 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages

Powered by phpBB® Forum Software