麻将中的基本胡牌算法--移除法

local pai = {1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 6, 6, 6}
-- local pai = {1,2}

--[[
1.去除一对
2.去除三个一样的
3.去除顺子
--]]

-- 深度复制表
function CopyTable(old_tab)
    if (type(old_tab) ~= "table") then -- 非表类型
        return nil
    end
    local new_tab = {}
    for i,v in pairs(old_tab) do
        local vtyp = type(v)
        if (vtyp == "table") then
            new_tab[i] = CopyTable(v)
        elseif (vtyp == "thread") then
            new_tab[i] = v
        elseif (vtyp == "userdata") then
            new_tab[i] = v
        else
            new_tab[i] = v
        end
    end
    return new_tab
end

-- 移除顺子
function RemoveStraight(t)
    if #t%3 == 0 and #t > 0 then
        local ret = {} -- 移除顺子后的表
        for i=1,#t - 2 do
            local found1
            local found2
            local position = {}
            table.insert(position,i)
            for k = i,#t do
                if not found1 and t[i] + 1 == t[k] then -- 找t[i] + 1的位置
                    found1  = true 
                    table.insert(position,k)
                end 

                if not found2 and t[i] + 2 == t[k] then -- 找t[i] + 2的位置
                    found2  = true 
                    table.insert(position,k)
                end 

                if found2 and found1 then -- 都找到了的话跳出循环
                    break
                end
            end
            if found2 and found1 then
                for i = #position,1,-1 do
                    table.insert(ret,table.remove(t,position[i])) -- 移除记录的位置并保存到ret表
                end
                return true,ret
            else
                return false
            end
        end
    else
        return false
    end
end

-- 移除三个一样的
function RemoveThreeSame(t)
    if #t%3 == 0 and #t > 0 then
        local found = false -- 是否找到三个一样的
        local begin -- 在第几个位置找到的
        for i=1,#t - 2 do
            if t[i] == t[i + 1] and t[i] == t[i + 2] then
                found = true
                begin = i
                break
            end
        end
        if found then -- 找到,则移除三次这个元素
            local ret = {}
            for k=1,3 do
                table.insert(ret,table.remove(t,begin))
            end
            return true,ret -- 返回ret以便递归
        else
            return false
        end
    else
        return false
    end
end

-- 递归去除
function Check3n(t)
    if #t%3 == 0 then
        local t1 = CopyTable(t)
        local t2 = CopyTable(t)
        if RemoveThreeSame(t1) then -- 去除DDD之后如果还有剩余,则会继续移除ABC,当两个条件都为false的时候,则return false
            if #t1 == 0 or Check3n(t1) then
                return true
            end
        end
        if RemoveStraight(t2) then
            if #t2 == 0 or Check3n(t2) then
                return true
            end
        end
        return false
    else
        return false
    end
end

-- 判断是否能胡牌
function CheckIsHu(tab)
    if #tab%3 == 2 then -- 不符合基础规则
        table.sort(tab, function(a, b) return a < b end) -- 排序
        for i = 1, #tab - 1 do
            if tab[i] == tab[i + 1] then -- 如果两个数相同，则求Tn
                local need_check = {}
                for k = 1, #tab do
                    if k ~= i and k~= i + 1 then
                        table.insert(need_check, tab[k])
                    end
                end
                -- 做除去对子之后的检验
                if #need_check == 0 or Check3n(need_check) then
                        return true
                else
                    return false
                end
            end
        end
        return false --没有找到对子
    else
        return false
    end
end

-- 测试耗时
local start_time = os.clock()
local is_hu = CheckIsHu(pai)
local end_time = os.clock()

print(string.format("end time   : %.4f", start_time));
print(string.format("end time   : %.4f", end_time));
print(string.format("cost time  : %.4f", end_time - start_time));
print("能否胡牌:"..tostring(is_hu))

研究了一晚上，睡觉睡觉。。。。