Re: Listing all Permutations using recursive function
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Listing all Permutations using recursive function
- From: Boyko Bantchev <boykobb@...>
- Date: 2005年8月18日 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)
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