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.