OpenEuphoria

Re: Project Programmer Wanter

• Posted by Juergen Luethje <jur at nurfuersp?m?de> Feb 07, 2008
• 900 views

Ret Law wrote:

> I am seeking a voluntary Euphoria programmer/s wishing to complete a project
> for general license (public Euphoria Library) involving permutation
> processing.
> 
> Please respond ASAP.

Sorry, I don't want to volunteer, but I can contribute a cool function:

global function next_permutation (sequence s)
   -- Return the next permutation of s (in lexicographic order);
   -- the function also works, if not all elements in s are distinguishable
   -- (meaning s is a multiset). For example, there are only
   -- 10 permutations of {1,1,2,2,2}, instead of 120.
   -- ** In order to get all possible permutations, initially sort s in
   --    ascending order. **
   -- [after
   --  Donald E. Knuth: TAOCP, Vol. 4, Fascicle 2 (2005), pp. 39 f.,
   --  "Algorithm 7.2.1.2 L"]
   -- Demo
   -- ----
   -- object x
   -- x = {"green", "blue", "red"}
   -- x = sort(x)
   -- while sequence(x) do
   --    ...
   --    x = next_permutation(x)
   -- end while
   object t
   integer n, i, j

   n = length(s)

   -- Step 1: Find the largest i such that s[i] can be increased.
   i = n - 1
   while i > 0 and compare(s[i],s[i+1]) != -1 do
      i -= 1
   end while
   if i = 0 then
      return -1                     -- end
   end if

   -- Step 2: Increase s[i] by the smallest feasible amount.
   j = n
   while compare(s[j],s[i]) != 1 do
      j -= 1
   end while
   t=s[i]  s[i]=s[j]  s[j]=t        -- swap s[i], s[j]

   -- Step 3: Reverse s[i+1..n]  (Find the lexicographically least
   --         way to extend the new s[1..i] to a complete pattern.)
   i += 1
   j = n
   while i < j do
      t=s[i]  s[i]=s[j]  s[j]=t     -- swap s[i], s[j]
      i += 1
      j -= 1
   end while

   return s
end function

Maybe this is useful for your project.

Regards,
   Juergen

-- 
http://luethje.eu/prog/