• Subject: Re: combination fun
• From: "Andrew Wilson" <agrwagrw@...>
• Date: Mon, 11 Sep 2006 12:28:08 -0400

Fix to sumtable function needed to get correct cross sums.   AGRW

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

On 9/11/06, Andrew Wilson <agrwagrw@gmail.com> wrote:
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)