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

Groups > comp.lang.forth > #10250

Set with unique members

Show all headers | View raw

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 :-)

-marcel

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

Thread

Set with unique members mhx@iae.nl (Marcel Hendrix) - 2012-03-20 20:24 +0200
  Re: Set with unique members Alex McDonald <blog@rivadpm.com> - 2012-03-20 15:24 -0700

csiph-web