OpenEuphoria

Re: k-subsets

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

I wrote:

> 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 ]-----------------------------


I have encountered a problem, which I don't understand.

The code above runs as expected, using the Windows interpreter (2.4 Beta).
That is, the output is:
 1) 'abc'
 2) 'abd'
 3) 'abe'
 4) 'acd'
 5) 'ace'
 6) 'ade'
 7) 'bcd'
 8) 'bce'
 9) 'bde'
10) 'cde'


Using the translator (2.4 Beta), and the Borland C++ 5.5 Command-line
Compiler, the output is:
 1) 'cde'
 2) 'cde'
 3) 'cde'
 4) 'cde'
 5) 'cde'
 6) 'cde'
 7) 'cde'
 8) 'cde'
 9) 'cde'
10) 'cde'


Does someone know what happens here? Are there any known problems with
recursion in translated programs?

Best regards,
   Juergen

-- 
 /"\  ASCII ribbon campain  |    |\      _,,,---,,_
 \ /  against HTML in       |    /,`.-'`'    -.  ;-;;,_
  X   e-mail and news,      |   |,4-  ) )-,_..;\ (  `'-'
 / \  and unneeded MIME     |  '---''(_/--'  `-'\_)