OpenEuphoria

Subsets

• Posted by Juergen Luethje <j.lue at gmx.de> Jun 16, 2007
• 609 views

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:

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

Regards,
   Juergen