OpenEuphoria

Re: Subsets

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

Pete,

here is the fastest binary solution which I have found so far.
It is about 20 times slower than the other function (after it has been
improved according to your suggestion).

include machine.e

sequence Subset_Buffer

function unrank_subset (integer n, integer rank)
   -- n: size of the set
   sequence bits
   integer k

   bits = int_to_bits(rank, n)
   k = 0
   for i = 1 to n do
      if bits[i] = 1 then
         k += 1
         Subset_Buffer[k] = i
      end if
   end for
   return k
end function
 

atom t
integer n, size

n = 24

-- generate all subsets
t = time()
Subset_Buffer = repeat(0, n)
for i = 0 to power(2,n)-1 do
   size = unrank_subset(n, i)
--    ? Subset_Buffer[1..size]
end for
t = time()-t
printf(1, "\n%.2f Sek.\n", {t})

if getc(0) then end if

Do you (or someone else) have any more suggestions?

Regards,
   Juergen