Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #43772

Re: Set with unique members

Show all headers | View raw

WJ wrote:

> > Marcel Hendrix wrote:
> > 
> > > This is ugly code from sumbrero:
> > > 
> > > : single2? ( a b -- bool ) = ; 
> > > 
> > > : single3? ( a b c -- bool ) 
> > > 	2DUP   = >R  
> > > 	2 PICK = >R  =  
> > > 	R> OR  
> > > 	R> OR ;
> > > 
> > > : single4? ( a b c d -- bool ) 
> > > 	LOCALS| d c b a | 
> > > 	a b =     a c = OR  a d = OR   
> > > 	b c = OR  b d = OR   
> > > 	c d = OR ;
> > > 
> > > ... which is used to test if in a set S with n elements
> > > all elements are unique, i.e when x in S, then no other 
> > > element y of S is equal to x.
> > > 
> > > Is there are better (faster, smaller) algorithm to do this?
> > > 
> > > I can think of trying to store all elements of S in a 
> > > temporary array T, i.e  (not tested)
> > > 
> > >      T = zeros(length(S))
> > >      for n = 0 to length(S)-1
> > >        if ( T[S[n]] ) return NOTUNIQUE 
> > >        else T[S[n]] = 1 
> > >      end
> > >      return OK
> > > 
> > > This would work if the elements of S are not too large
> > > (say characters, bytes, 16-bit words).
> > > 
> > > When the elements of S are 32 or 64 bit numbers, strings 
> > > or whatnot, a suitable hash function could be defined.
> > > 
> > > But I hope for something much simpler :-)

Ocaml:

module Ls = List;;

let set = [0;1;2;3;4;5;6;7;8;9;0] in
    Ls.sort compare set = Ls.sort_uniq compare set ;;
 ===>
false

let set = [0;1;2;3;4;5;6;7;8;9] in
    Ls.sort compare set = Ls.sort_uniq compare set ;;
 ===>
true

Back to comp.lang.forth | Previous | Next | Find similar | Unroll thread

Thread

Re: Set with unique members "WJ" <w_a_x_man@yahoo.com> - 2015-11-25 18:59 +0000

csiph-web