OpenEuphoria

Re: Subsets

• Posted by CChris <christian.cuvier at agriculture.gouv.fr> Jun 16, 2007
• 615 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