Re: Subsets
- Posted by CChris <christian.cuvier at agriculture.gouv.fr> Jun 16, 2007
- 602 views
Juergen Luethje wrote: > > Hi all, > > I've written functions for generating (indexes of) all subsets of a given set. > They don't use recursion and are easy to use, and they are not too slow. > However, since a set with n elements has power(2,n) subsets, I'd like to ask > whether maybe someone can give me faster routines. Here are mine: > }}} <eucode> > sequence S > integer N, K > > global function first_subset (integer n) > -- in: n: number of elements in the set > S = repeat(0, n+1) > N = n > K = 1 > return {} > end function > > global function next_subset() > if S[K] < N then > K += 1 > S[K] = S[K-1] + 1 > return S[2..K] > elsif K > 2 then > K -= 1 > S[K] += 1 > return S[2..K] > else > return -1 > end if > end function > > > -- Demo > object subset > integer n > > n = 4 > > -- generate all subsets in order > subset = first_subset(n) > while sequence(subset) do > ? subset > subset = next_subset() > end while > </eucode> {{{ > Regards, > Juergen Did you try the routines in http://oedoc.free.fr/Fichiers/ESL/sets.zip ? I have no idea whether they are faster, but some of them to that precise work. CChris