OpenEuphoria

re: permutation

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

This C++ function from STL works like I want it to:

// TEMPLATE FUNCTION next_permutation
template<class _BI> inline
 bool next_permutation(_BI _F, _BI _L)
 {_BI _I = _L;
 if (_F == _L || _F == --_I)
  return (false);
 for (; ; )
  {_BI _Ip = _I;
  if (*--_I < *_Ip)
   {_BI _J = _L;
   for (; !(*_I < *--_J); )
    ;
   iter_swap(_I, _J);
   reverse(_Ip, _L);
   return (true); }
  if (_I == _F)
   {reverse(_F, _L);
   return (false); }}}


I translated that above to this Euphoria code and it doesn't work, any
help?:

--// template<class _BI> inline
--//  bool next_permutation(_BI _F, _BI _L)
global function next_permutation (sequence s)
    integer F, L, I, Ip, J, I_old
    F = 1
    L = length (s)

    --// _BI _I = _L;
    I = L

    --// if (_F == _L || _F == --_I)
    --//     return (false);
    if (F = L or F = I - 1) then
        return {false}
    end if

    --// for (; ; )
    --// {
    while 1 do
    --//     _BI _Ip = _I;
             Ip = I
    --//     if (*--_I < *_Ip)
    --//     {
             if (compare (s [I], s [Ip]) = -1) then
    --//         _BI _J = _L;
                 J = L
                 I -= 1
    --//
    --//         for (; !(*_I < *--_J); );
                 while not (compare (s [I], s [J]) = -1) do
                    J -= 1
                 end while
    --//         iter_swap(_I, _J);
                 I_old = I
                 I = J
                 J = I_old
    --//         reverse(_Ip, _L);
                 s = s [1 .. Ip - 1] & reverse (s [Ip .. L])
    --//         return (true);
                 return {true, s}
    --//     }
             else
                 I -= 1
             end if
    --//     if (_I == _F)
             if (I = F) then
    --//     {
    --//         reverse(_F, _L);
    --//         return (false);
                 return {false, reverse (s)}
    --//     }
             end if
    --// }
    end while
end function



this is to test:

procedure test_next_permutation ()
    sequence s, res
    s = {1,2,3}
    for i = 1 to 10 do
        res =  next_permutation (s)
        --// ?res
        --// if res [1] = false then
            --// exit
        --// end if
        s = res [2]
        ? s
    end for
end procedure







Here's another one i tried:

--// template <class _BidirectionalIter>
--// bool next_permutation(_BidirectionalIter __first, _BidirectionalIter
__last) {
global function next_permutation2 (sequence s)
    integer first, last, i, ii, j, i_old
    first = 1
    last = length (s)
--//   __STL_DEBUG_CHECK(__check_range(__first, __last))
--//   if (__first == __last)
--//     return false;
       if (first = last) then
           return {false}
       end if
--//   _BidirectionalIter __i = __first;
--//   ++__i;
       i = first + 1
--//   if (__i == __last)
--//     return false;
       if (i = last) then
           return false
       end if
--//   __i = __last;
--//   --__i;
       i = last
       i -= 1
--//
--//   for(;;) {
       while 1 do
--//     _BidirectionalIter __ii = __i;
         ii = i
--//     --__i;
         i -= 1
--//     if (*__i < *__ii) {
         if (compare (s [i], s [ii]) = -1) then
--//       _BidirectionalIter __j = __last;
           j = last
--//       while (!(*__i < *--__j))
--//         {}
           j -=1
           while not (compare (s [i], s [j]) = -1) do
               j -= 1
           end while
--//       iter_swap(__i, __j);
           i_old = i
           i = j
           j = i_old
--//       reverse(__ii, __last);
           s = s [1 .. ii - 1] & reverse (s [ii .. last])
--//       return true;
           return {true, s}
--//     }
         end if
--//     if (__i == __first) {
         if (i = first) then
--//       reverse(__first, __last);
--//       return false;
           return {false, reverse (s)}
--//     }
         end if
--//   }
       end while
--// #if defined(__STL_NEED_UNREACHABLE_RETURN)
--//     return 0;
--// #endif
--// }
end function