Re: Listing all Permutations using recursive function

[Boyko Bantchev <boykobb@...>]

On 8/16/05, Szilard <szilard@int.com> wrote:
> My question is about recursive funtions.
> Lets say I want to write a function list_perm(n) that will list
> for me all the permutations of 1,2,...n

One of the many ways to do this (not the simplest one)
is the following, where each permutation is obtained
from the previous one by only exchanging two adjacent
items (and the same connection relates the last permutation
with the first one).  The method is essentially recursive,
but instead of recursion, the implementation makes use of
chained coroutines (as this has several advantages over
recursion).

...............................................
function cptb(a,n)
  local b = {}
  for i=1,n  do b[i] = a[i] end
  return b
end

function gprm(a)
  local function gp(m,g)
    return coroutine.create(
      function()
        local pos = coroutine.wrap(
          function()
            while true do
              for x=m,1,-1 do coroutine.yield(x) end
              for x=1,m do coroutine.yield(x) end
            end
          end)
        local b,i,j  j = m
        while true do
          i = pos()
          if i==j then
            _,b = coroutine.resume(g)
            if coroutine.status(g)=='dead' then return end
            b = cptb(b,m-1)  table.insert(b,i,a[m])
          else
            if i<j then j = i end
            b[j],b[j+1] = b[j+1],b[j]
          end
          coroutine.yield(b)
          j = i
        end
      end)
    end
  local f = coroutine.create(function() coroutine.yield{} end)
  for i=1,table.getn(a) do f = gp(i,f) end
  return f
end

-- example of use:

a = {'a','b','c','d','e'}
c = gprm(cptb(a,4))        -- use one of 0,1,...,5 here
while true do
  _,p = coroutine.resume(c)
  if coroutine.status(c)=='dead' then break end
  print(table.concat(p,' '))
end