OpenEuphoria

k-subsets

• Posted by Juergen Luethje <j.lue at gmx.de> May 10, 2003
• 361 views

Hi all,

I wrote a small function, that returns all subsets of a given set,
containing exactly 'k' elements. It seems to work fine, I'm just
wondering whether there are faster algorithms. Any ideas?

----------------------------[ BEGIN CODE ]----------------------------
sequence Ret, Set, Choice
integer D, K, Id

procedure find_subsets (integer v)
   for i = v to D+Id do
      Choice[Id] = Set[i]
      if Id = K then
         Ret = append(Ret, Choice)
      else
         Id += 1
         find_subsets(i+1)
         Id -= 1
      end if
   end for
end procedure

global function k_subsets (sequence set, integer k)
   -- return all subsets of 'set', containing exactly 'k' elements
   Ret = {}
   if k > 0 then
      Set = set
      Choice = repeat(0, k)
      D = length(set)-k
      K = k
      Id = 1
      find_subsets(1)
   end if
   return Ret
end function

-- Demo
sequence s
s = k_subsets("abcde", 3)
for i = 1 to length(s) do
   printf(1, "%2d) '%s'\n", {i, s[i]})
end for
-----------------------------[ END CODE ]-----------------------------

Best regards,
   Juergen

-- 
 /"\  ASCII ribbon campain  |
 \ /  against HTML in       |  This message has been ROT-13 encrypted
  X   e-mail and news,      |  twice for higher security.
 / \  and unneeded MIME     |