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.