OpenEuphoria

re: permutation

• Posted by tone.skoda at siol.net May 30, 2002
• 554 views

I figured it out, I first simplified it in C++ and then it worked in
Euphoria.
Here it is if some one will need it some time:

--/*
-- next_permutation [Created on 30. May 2002, 21:02]
-- The 'next_permutation' function is translation of
-- C++ STL function with same name.
-- It differs from 'Permutation ()' from genfunc.e
-- that this function doesn't get duplicated combinations if you
-- have some equal members in sequence.
--
-- For example, for "AAC" this is returned from these functions:
--
-- Permutation ()   next_permutation ():
--     AAC                AAC
--     ACA                ACA
--     AAC                CAA
--     ACA
--     CAA
--     CAA
--
--
-- PARAMETERS
-- 's'
--    sequence to permutate. It should be sorted, ascending?.
--    You can use s = sort (s) to sort it.
--
-- RETURN VALUES
-- Sequence with these two values:
-- 1. true if we got new combination
--    or false if we got some of the older combinations, that means that
we're going round'n round.
--    Check for this in loop, if it is false exit from loop.
-- 2. the permutation, sequence.
--
-- EXAMPLE CODE
--
-- sequence s, res
-- s = {'B','A','C'}
-- s = sort (s)
-- puts (1, s & "\n")
-- while 1 do
--     res =  next_permutation (s)
--     if res [1] = false then
--         exit
--     end if
--     s = res [2]
--     puts (1, s & "\n")
-- end while
--
--*/
global function next_permutation (sequence s)
    integer F, L
    integer I
    integer Ip, J
    object s_i_old
    F = 1
    L = length (s)
    I = L
    if (F = L or F = I) then
        return {false}
    end if
    while (1) do
        Ip = I
        I -= 1
        if (compare (s [I], s [Ip]) = -1) then
            J = L
            while (1) do
                if (compare (s [I], s [J]) = -1) then
                    exit
                end if
                J -= 1
            end while
            s_i_old = s [I]
            s [I] = s [J]
            s [J] = s_i_old
            s = s [1 .. Ip - 1] & reverse (s [Ip .. length (s)])
            return {true, s}
        end if
        if (I = F) then
            s = reverse (s [F .. length (s)])
            return {false, s}
        end if
    end while
end function