OpenEuphoria

Re: Subsets

• Posted by Pete Lomax <petelomax at blueyonder.co.uk> Jun 18, 2007
• 600 views

Juergen Luethje wrote:
> 
> 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).
This is what I meant, perhaps I sould have called it a boolean array:

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, t1, t2
integer n, size

function getNextSet()
    for i=n to 1 by -1 do
	if Subset_Buffer[i]=0 then
	    Subset_Buffer[i]=1
	    return 1
	end if
	Subset_Buffer[i]=0
    end for
    return 0
end function
 

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
t1 = time()-t

t=time()
Subset_Buffer = repeat(0, n)
while 1 do
    if not getNextSet() then exit end if
end while
t2 = time()-t
printf(1, "\nt1=%.2f, t2=%.2f\n", {t1,t2})

if getc(0) then end if

Seems about the same 20-fold faster, but uses flags not indexes.

Regards,
Pete