OpenEuphoria

Re: Re[4]: How to make routine like this

• Posted by rforno at tutopia.com Dec 14, 2001
• 515 views

Aku:
I sent to the list another routine, that was tested and is very fast. You
might not have noticed it, so I am including it next now:

function var (sequence set, integer size, integer which)
    integer c, len, a

    if size <= 0 then
 return {}
    elsif size = 1 then
 return {set[which]}
    end if

    len = length(set)
    c = 1
    for i = len - size + 1 to len - 1 do
 c *= i
    end for

    a = floor((which - 1) / c)
    which -= a * c
    a += 1
    return set[a] & var(set[1..a - 1] & set[a + 1..len], size - 1, which)
end function

for i = 1 to 60 do
    ? var({1, 2, 3, 4, 5}, 3, i)
end for



----- Original Message -----
From: <aku at inbox.as>
To: "EUforum" <EUforum at topica.com>
Sent: Friday, December 14, 2001 11:12 AM
Subject: Re[4]: How to make routine like this


>
>
> I think this is wrong...
>
> I get 151200 for ? get_permutation( digits, 5, 0 )
>
> but I can't repair the problem ( I don't understand. )
>
> Can you correct that? Thanks!
>
> e> Warning! Untested:
>
> e> function get_permutation(sequence symbolSet, integer len, integer
> e> permutation)
> e>     sequence remaining, out
> e>     integer max, pos, divisor, element
> e>     integer setLength
>
> e>     setLength = length(symbolSet)
>
> e>     -- Calculate total mumber of permutations and generate an index
list
> e>     max = 1
> e>     remaining = repeat(0, setLength)
> e>     for i = 1 to setLength
> e>         remaining[i] = i
> e>         if i >= len then
> e>             max *= i
> e>         end if
> e>     end for
>
> e>     -- Actions based on permutation number
> e>     if permutation = 0 then
> e>         -- Handy for calculating exactly how many permutations there
are
> e>         return max
> e>     elsif not (1 <= permutation and permutation <= max) then
> e>         -- There are no permutations outside the 1..max range
> e>         return -1
> e>     end if
>
> e>     -- Generate the output using some cunning math(s)
> e>     out = {}
> e>     pos = permutation
> e>     divisor = max
>
> e>     for i = 1 to len do
> e>         divisor /= len - i + 1
> e>         element = floor(pos / divisor)
> e>         pos -= divisor * element
> e>         element += 1
> e>         out &= symbolSet[remaining[element]]
> e>         remaining =
> e>             remaining[1..element-1] &
> e>             remaining[element+1..length(remaining)]
> e>     end for
> e>     return out
> e> end function
>
> e> sequence digits
> e> digits = {0,1,2,3,4,5,6,7,8,9}
>
> e> ? get_permutation( digits, 5, 0 )
> e> -- prints the number of permutations of 'digits' with 5 elements.
> e> -- (should be 30240)
>
> e> ? get_permutation( digits, 5, 50000 )
> e> -- prints -1 -- there is no 50000th 5-digit permutation of 'digits'.
>
> e> ? get_permutation( digits, 5, 29050 )
> e> -- prints the 29050th 5-digit permutation of 'digits'
>
> e> To generate all possible combinations like last time:
>
> e> for i = 1 to get_permutation( digits, 5, 0 ) do
> e>     ? get_permutation( digits, 5, i )
> e> end for
>
> e> HTH,
> e> Carl
>
>
>
>