# Combination Algorithms and the Natural Logarithm Base

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```