# Generating permutations

For some experiment I’m conducting, I needed to generate all permutations given a number of slots and a number of symbols. I also didn’t want to use built-in libraries like Python or other languages have to generate them, so I picked Lua to avoid being tempted to do so (and because its a cool language).

Now there are Lua implementations to do this, for example on Rosetta Code but the all examples I’ve seen either use recursion or appeared oversized.

I wrote the following non-recursive function in Lua to generate permutations given as input a number of slots and a number of symbols.

```-- generate permutations
-- input a, b (a number of slots, b number of symbols)
function permutations(a,b)
if a==0 then return end
local taken = {}
local slots = {}
for i=1,a do slots[i]=0 end
for i=1,b do taken[i]=false end
local index = 1
while index > 0 do repeat

repeat
slots[index] = slots[index] + 1
until slots[index] > b or not taken[slots[index]]

if slots[index] > b then
slots[index] = 0
index = index - 1
if index > 0 then
taken[slots[index]] = false
end
break
else
taken[slots[index]] = true
end

if index == a then
for i=1,a do
io.write( slots[i] )
io.write( " " )
end
io.write( "n")
taken[slots[index]] = false
break
end

index = index + 1
until true end
end```

The following is in generator form:

```function perm( sl, sy )
local permutations = function( a,b )
if a==0 then return end
local taken = {}
local slots = {}
for i=1,a do slots[i]=0 end
for i=1,b do taken[i]=false end
local index = 1
while index > 0 do repeat
repeat
slots[index] = slots[index] + 1
until slots[index] > b or not taken[slots[index]]
if slots[index] > b then
slots[index] = 0
index = index - 1
if index > 0 then
taken[slots[index]] = false
end
break
else
taken[slots[index]] = true
end
if index == a then
coroutine.yield(slots)
taken[slots[index]] = false
break
end
index = index + 1
until true end
end

return coroutine.wrap(function () permutations(sl, sy) end)
end

function test(a,b)
ci = perm(a,b)
a = ci()
while a~=nil do
for i=1,#a do
io.write( a[i] )
io.write( " " )
end
io.write( "n")
a = ci()
end
end```

This method can probably be improved since it goes over all possible combinations (both repeating and non-repeating) and in the process filters out the repeating ones.

This site uses Akismet to reduce spam. Learn how your comment data is processed.