• Subject: A question about the implement the Integer Partitions
• From: sagasw <sagasw@...>
• Date: Tue, 29 Dec 2009 22:04:27 +0800

I want to implement the Integer Partitions algorithm,
http://www.cs.sunysb.edu/~algorith/files/generating-partitions.shtml

And I use the following code could work.

But following code has a critical issue, it is very slow in large number and need very large memory,
in my test, if the input number is 50, it needs about 1G memory for lua.exe.

Could you have any comment about improving the code?

sagasw

--------------------------------------------------------------------------
function JoinTables(t1, t2)
for k,v in ipairs(t2) do table.insert(t1, v) end
return t1
end

local globalresult = {}
local globalposition = 1

function IntegerPartitions(fix_table, divN, limitN)
if divN == 2 then
local resultT = {1, 1}
JoinTables(resultT, fix_table)
table.insert(globalresult, globalposition, resultT)
globalposition = globalposition + 1
resultT = nil
return
end

for fixed = limitN, 1, -1 do
local number2 = divN - fixed
if fixed >= number2 and fixed <= limitN then
local resultT = {}
JoinTables(resultT, fix_table)
if number2 == 0 then
JoinTables(resultT, {fixed})
else
JoinTables(resultT, {fixed, number2})
end

table.insert(globalresult, globalposition, resultT)
globalposition = globalposition + 1
resultT = nil

if number2 > 1 then
local resultT2 = {fixed}
JoinTables(resultT2, fix_table)
IntegerPartitions(resultT2, number2, number2 -1)
resultT2 = nil
end
end

if number2 > 1 and fixed < number2 then

local resultT2 = {fixed}
JoinTables(resultT2, fix_table)
IntegerPartitions(resultT2, number2, fixed)
resultT2 = nil
end
end
end

IntegerPartitions({}, 50, 50)
--------------------------------------------------

------------------------------------
C++, Lua, living in Dalian
http://sunxiunan.com/