OpenEuphoria

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

• Posted by euphoria at carlw.legend.uk.com Dec 13, 2001
• 384 views

<aku at inbox.as> wrote:

> Thanks!
>
> But are there better solutions, without checking duplicate
> digits in in the left? Because I need it to be very fast.

Warning! Untested:

function get_permutation(sequence symbolSet, integer len, integer
permutation)
    sequence remaining, out
    integer max, pos, divisor, element
    integer setLength

    setLength = length(symbolSet)

    -- Calculate total mumber of permutations and generate an index list
    max = 1
    remaining = repeat(0, setLength)
    for i = 1 to setLength
        remaining[i] = i
        if i >= len then
            max *= i
        end if
    end for

    -- Actions based on permutation number
    if permutation = 0 then
        -- Handy for calculating exactly how many permutations there are
        return max
    elsif not (1 <= permutation and permutation <= max) then
        -- There are no permutations outside the 1..max range
        return -1
    end if

    -- Generate the output using some cunning math(s)
    out = {}
    pos = permutation
    divisor = max

    for i = 1 to len do
        divisor /= len - i + 1
        element = floor(pos / divisor)
        pos -= divisor * element
        element += 1
        out &= symbolSet[remaining[element]]
        remaining =
            remaining[1..element-1] &
            remaining[element+1..length(remaining)]
    end for
    return out
end function

sequence digits
digits = {0,1,2,3,4,5,6,7,8,9}

? get_permutation( digits, 5, 0 )
-- prints the number of permutations of 'digits' with 5 elements.
-- (should be 30240)

? get_permutation( digits, 5, 50000 )
-- prints -1 -- there is no 50000th 5-digit permutation of 'digits'.

? get_permutation( digits, 5, 29050 )
-- prints the 29050th 5-digit permutation of 'digits'

To generate all possible combinations like last time:

for i = 1 to get_permutation( digits, 5, 0 ) do
    ? get_permutation( digits, 5, i )
end for

HTH,
Carl