A question about the implement the Integer Partitions

[sagasw <sagasw@...>]

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? 

please help me review it, thanks,

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/
http://twitter.com/sagasw
------------------------------------