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  
 
 [ 5 post ] 

 Relevant Pages 

1. list-directed read statement works in different way on different platforms

2. Anybody know why I am timing out

3. I know. I am full of it

4. Assignments of INTEGERS with different ranges

5. Different fonts in List Boxes

6. different LISTS on TABS

7. Formatting Different Styles in List Box

8. Items in different color in list widget

9. Items in different color in list widget

10. Different representations of same field in browse list

11. Not the same focus record while 2 list box in different tabs

12. CA Cans VO ?

 

 
Powered by phpBB® Forum Software