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