While comparing the efficiency of my iterative method for generating combinations vs. the recursive method shown at the Rosetta Code site I picked up on a pattern that at first glance is not obvious so I’m still looking into it. It seems that the ratio of the efficiency between the algorithms seems to approach the natural logarithm base (2.71828182…)

Here’s the code – I’ll do some more research before attempting to explain what is going on here

------------------------------------------------------------------------------
-- Lua recursive code for generating combinations from Rosetta Code
function map(f, a, ...)
    c1=c1+1
    if a then return f(a), map(f, ...) end
end

function incr(k)
    return function(a) return k > a and a or a+1 end
end

function combs1(m, n)
    if m * n == 0 then return {{}} end
    local ret, old = {}, combs1(m-1, n-1)
    for i = 1, n do
        for k, v in ipairs(old) do
            ret[#ret+1] = {i, map(incr(i), unpack(v))}
        end
    end
    return ret
end

--for k, v in ipairs(combs(3, 5)) do print(unpack(v)) end

-----------------------------------------------------------------------------
-- My Lua iterative code for generating combinations
-- input a, b (a number of slots, b number of symbols)
function combs2(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
            c2=c2+1
            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

------------------------------------------------------
-- A comparison of the number of operations required
-- by recursive and non-recursive method. Tests show
-- that as the number of slots and symbols rise, the
-- ratio of the efficiency shows an interesting pattern
-- and has to do with the base of the natural logarithm
-------------------------------------------------------

function compare(sl,sy)
    c1=0
    c2=0
    combs1(sl, sy)
    combs2(sl, sy)
    print( "slots:"..sl..", symbols:"..sy.." => iterative/recursive ratio:"..c2/c1)
end

for n=2,11 do
    compare(n,n)
end