• Subject: Re: Listing all Permutations using recursive function
• From: Boyko Bantchev <boykobb@...>
• Date: Thu, 18 Aug 2005 18:06:19 +0300

```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)
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)