lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


I've been playing around with combinations to generate some kakuro (cross sum) tables, but wonder if combination implementation is very efficient or optimal? So here is a little combinations iterator & sample code,  can the lua code be smaller, faster, more lua?  Should coroutines be used?

Any feedback welcome,
thanks AGRW


-- Combinations with lua.
--for i,v in combinations( table, combinesize) do
--    print(i,table.concat(v," "))
--end
--

-- make clone of table
function clone(t)
    local n={}
    for i=1,#t do n[i]=t[i] end
    return n
end

function insertvalue(t,v)
    -- insert set[i] to each table
    for j=1,#t do
        table.insert(t[j],1,v)
    end
end

function copytable(t1,t2)
    -- insert all values of t2 to t1
    for j,v in ipairs(t2) do
        table.insert(t1,v)
    end
end

-----------------------------------------------------------
-- function generateCombinations(originalTable,combinesize)
--   recursively generate table of all combinations
-----------------------------------------------------------
function generateCombinations(originalTable,combinesize)

    local combinationTable={}

    if #originalTable < combinesize then
       return combinationTable
    end

    -- if combine size is one return all elements in table
    if combinesize == 1 then

        for i = 1, #originalTable do
            table.insert(combinationTable,{originalTable[i]})
        end  

    else
   
        local copyOriginalTable=clone(originalTable)

        for i =1,#originalTable-1 do
    
            -- take each element in original table and add it to all
            -- combinations of original table with element remove
            -- with combinesize - 1
       
            -- remove element
            table.remove(copyOriginalTable,1)       
       
            -- get combinations of combinesize-1 with element removed from originalTable
            local mergeTable = generateCombinations(copyOriginalTable,combinesize-1)
      
            -- add originTable element to each returned combine size
            insertvalue(mergeTable,originalTable[i])
       
            -- copy merged result of element and combinatoins into final combinationTable
            copytable(combinationTable,mergeTable)

        end
       
    end

    return combinationTable

end--function generateCombinations

----------------------------------
-- function combinations(t,csize)
--   combination iterator
----------------------------------
function combinations(t,csize)

    local ctable=generateCombinations(t,csize)

    local function citer(t,i)
              i=i+1
              local v=ctable[i]
              if v then
                 return i,v
              end
          end

    return citer,t,0
end


-- FIRST COMBINATION EXAMPLE
t={"a","b","c","d","e"}
print("\n1st example all combinations of 3 elements of table {"..table.concat(t," ").."}\n")
for i,v in combinations({"a","b","c","d","e"},3) do
    print(i,table.concat(v," "))
end

-- SECOND COMBINATION EXAMPLE
print("\n2nd example all clue/squares for kakuro/crosssums")
print("All Crossums or kakuro clue/squares table:\n")


-- sum elements in a table
function sumtable(t)
    local sum=0
     for v in pairs(t) do    
        sum = sum + v      
    end--for
    return sum  
end--function

local totalsolutions=0
for numberofsquares=2,9 do
    for cluenumber=3,45 do

        for i,v in combinations({1,2,3,4,5,6,7,8,9},numberofsquares) do
            if sumtable(v)==cluenumber then
                print(string.format ("clue=%02d squares=%02d  :  %s",cluenumber,numberofsquares,table.concat(v," "))) 
                totalsolutions=totalsolutions+1
            end          
        end

    end
end
print("\nTotal number of kakuro clue/squares solutions is "..totalsolutions)