带N个癞子的胡牌算法

ps：该算法还没有在写法封装上进一步优化，但是性能已经很好了，判断一次需要的时间基本为0（太小忽略）,明天继续优化。。。

1.基本胡牌的算法（无癞子），一个数列，满足 N * ABC + M *DDD +ＥＥ 即可

思路：先从牌中找出一对EE，再去剩余的牌中找出一个DDD，再去剩余的牌中找出一个ABC，以此递归，最后剩余无牌即胡牌

2.带N个癞子的胡牌算法

思路：先从牌中找出一对EE，找不到用癞子去补足癞子....以此类推

print("--------------基本胡牌算法-------------")
--[[
1.去除一对
2.去除三个一样的
3.去除顺子
--]]

local remove_attr = {}

-- 深度复制表
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 == 2 then
        if t[1] + 1 == t[2] then
            l_num = l_num - 1
            if l_num >= 0 then
                -- 存起来
                local temp = {}
                table.insert(temp, t[#t] + 1)
                for i = 1, 2 do
                    table.insert(temp, table.remove(t, 1))
                end
                table.sort(temp)
                temp[3] = tostring(temp[3])
                temp[4] = "RemoveStraight"
                table.insert(remove_attr, temp)
                return true
            end
        end
        
        if t[1] + 2 == t[2] then
            l_num = l_num - 1
            if l_num >= 0 then
                -- 存起来
                local temp = {}
                table.insert(temp, t[1] + 1)
                for i = 1, 2 do
                    table.insert(temp, table.remove(t, 1))
                end
                table.sort(temp)
                temp[2] = tostring(temp[2])
                temp[4] = "RemoveStraight"
                table.insert(remove_attr, temp)
                return true
            end
        end
        
        return false
    end
    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
            local temp = {}
            for i = 1, #position do
                table.insert(temp, t[position[i]])
            end
            temp[4] = "RemoveStraight"
            table.insert(remove_attr, temp)
            
            for i = #position, 1, -1 do
                table.remove(t, position[i])
            end
            return true, temp
        end
        -- 没找到顺子
        if found1 and not found2 then
            if l_num >= 1 then -- 有足够赖子
                l_num = l_num - 1
                -- 存起来
                local temp = {}
                table.insert(temp, t[position[#position]] + 1)
                for i = #position, 1, -1 do
                    table.insert(temp, table.remove(t, position[i]))
                end
                table.sort(temp)
                temp[3] = tostring(temp[3])
                temp[4] = "RemoveStraight"
                table.insert(remove_attr, temp)
                return true
            end
        end
        if not found1 and found2 then
            if l_num >= 1 then -- 有足够赖子
                l_num = l_num - 1
                -- 存起来
                local temp = {}
                table.insert(temp, t[position[#position]] - 1)
                for i = #position, 1, -1 do
                    table.insert(temp, table.remove(t, position[i]))
                end
                table.sort(temp)
                temp[2] = tostring(temp[2])
                temp[4] = "RemoveStraight"
                table.insert(remove_attr, temp)
                return true
            end
        end
    end
    return false
end

-- 移除三个一样的
function RemoveThreeSame(t)
    local found = false -- 是否找到三个一样的
    local found_half1 = false -- 有赖子的情况找到两个一样的，其余用赖子代替
    local found_half2 = false
    local begin -- 在第几个位置找到的
    
    if #t == 2 then -- 只有两个且相等
        if t[1] == t[2] then
            found_half1 = true
            begin = 1
        end
    end
    
    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
        if t[i] == t[i + 1] and not t[i] == t[i + 2] then
            found_half1 = true
            begin = i
            break
        end
        if not t[i] == t[i + 1] and t[i] == t[i + 2] then
            found_half2 = true
            begin = i
            break
        end
    end
    
    if found then -- 找到,则移除三次这个元素并记录到ret
        local ret = {}
        for k = 1, 3 do
            table.insert(ret, table.remove(t, begin))
        end
        ret[4] = "RemoveThreeSame"
        table.insert(remove_attr, ret)
        return true, ret
    end
    
    if found_half1 then -- 某个条件符合，但是另一个条件不符合的时候
        print("in half1")
        if l_num >= 1 then
            l_num = l_num - 1
            
            -- 存起来
            local temp = {}
            for s = 1, 2 do
                table.insert(temp, t[begin])
            end
            table.insert(temp, tostring(t[begin]))
            ret[4] = "RemoveThreeSame"
            table.insert(remove_attr, temp)
            
            for k = 1, 2 do
                table.remove(t, begin) -- 移除第一个和第二个
            end
            return true
        end
    end
    
    if found_half2 then
        if l_num >= 1 then
            l_num = l_num - 1
            
            -- 存起来
            local temp = {}
            for s = 1, 2 do
                table.insert(temp, t[begin])
            end
            table.insert(temp, tostring(t[begin]))
            ret[4] = "RemoveThreeSame"
            table.insert(remove_attr, temp)
            
            table.remove(t, begin)
            table.remove(t, begin + 1) -- 移除第一个和第三个
            return true
        end
    end
    
    return false
end

-- 递归去除
function Check3n(t)
    if (#t + l_num) % 3 == 0 then
        if #t == 1 then
            table.insert(remove_attr, {string.format("只剩一个\"%d\"了，赖子还有%d个，可以胡", t[1], l_num)})
            return true
        end
        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 RemoveSomeFromTable(tab, remove_table)
    if #tab < #remove_table then return end
    local table_copy = CopyTable(tab)
    local new_table = {}
    for i = #remove_table, 1, -1 do
        table.remove(table_copy, remove_table[i])
    end
    new_table = table_copy
    return new_table
end

function CheckHave2n(tab)
    -- 找对子
    if #tab < 2 then return false end
    for i = 1, #tab - 1 do
        if tab[i] == tab[i + 1] then -- 如果两个数相同，则求Tn
            -- 存移除的对子
            local temp = {}
            temp[1] = tab[i]
            temp[2] = tab[i + 1]
            temp[3] = "RemoveDoubble_Have2n"
            table.insert(remove_attr, temp)
            local need_check = RemoveSomeFromTable(tab, {i, i + 1})
            if #need_check == 0 or Check3n(need_check) then
                return true
            end
        end
    end
    return false
end

function CheckNo2n(tab)
    if l_num < 0 then return false end
    l_num = l_num - 1
    -- 配一个对子的情况
    for i = 1, #tab do
        local need_check = RemoveSomeFromTable(tab, {i})
        if #need_check == 0 or Check3n(need_check) then
            table.insert(remove_attr, {tab[1], tostring(tab[1]), "RemoveDoubble_No2n"})
            return true
        end
    end
    -- 一轮下来没有返回true，说明配一个赖子不行，得配两个
    l_num = l_num - 1
    if l_num >= 0 then
        return RemoveStraight(tab) -- 移除顺子即可
    end
    return false
end

-- 判断是否能胡牌
function CheckIsHu(tab)
    if #tab % 3 == 2 then -- 不符合基础规则
        table.sort(tab, function(a, b) return a < b end) -- 排序
        
        l_num = 0 -- 赖子个数,全局变量
        local position = {} -- 记录赖子的位置
        for k, v in ipairs(tab) do
            if 99 == v then
                table.insert(position, k)
            end
        end
        for i = #position, 1, -1 do -- 移除赖子
            table.remove(tab, position[i])
        end
        l_num = #position -- 记录赖子的个数
        
        local tab_copy = CopyTable(tab)
        if not CheckHave2n(tab) then -- 没有找到对子
            if l_num > 0 then
                return CheckNo2n(tab_copy, l_num) -- 用赖子补的方法去做
            end
            return false
        else
            return true
        end
    else
        return false
    end
end

print("--------------带N个赖子的胡牌算法-------------")

--[[
有赖子的情况：
1.同样找出所有包含一对的情形，移除对子，移除的时候需要注意更新癞子的数量这里需要注意的是对子是怎么产生的: 
  原有的对子
  一个癞子和一普通的组成的对子
  一对癞子
2.针对每个数组尝试移除一个顺子，成功转到2，如果失败尝试用癞子去补，癞子也不够，转到3。
3.针对每个数组尝试移除一个刻子（DDD），成功转到2，如果失败尝试用癞子去补，癞子也不够，当前的方案就不通过。
4.若当前的数组的数量变为0，则表示，当前的方案可以胡牌。
--]]

-- 递归打印表
function PrintTable(tbl, level) -- level 为递归深度，默认为1
    local msg = ""
    level = level or 1
    local indent_str = "" -- 缩进
    for i = 1, level do
        indent_str = indent_str .. "  "
    end
    if level == 1 then
        print(indent_str .. "{")
    end
    for k, v in pairs(tbl) do
        local k_str = ""
        if type(k) == "string" then -- 键值为字符串，则["xxx"]
            k_str = string.format("[\"%s\"]", k)
        else
            k_str = string.format("[%s]", k)
        end
        if type(v) == "table" then
            local item_str = string.format("%s%s = {", indent_str .. "  ", k_str)
            print(item_str)
            PrintTable(v, level + 1)
        elseif type(v) == "number" then
            local item_str = string.format("%s%s = %s,", indent_str .. "  ", k_str, tostring(v))
            print(item_str)
        else
            local item_str = string.format("%s%s = \"%s\",", indent_str .. "  ", k_str, tostring(v))
            print(item_str)
        end
    end
    if level == 1 then
        print(indent_str .. "}")
    else
        print(indent_str .. "},")
    end
end

local res
-- local pai = {1, 99}
-- local pai = {1, 1, 99}
-- local pai = {1, 1, 2, 3, 99, 99, 99, 99}
-- local pai = {1, 3, 5, 8, 8, 99, 99, 99}
-- local pai = {1, 2, 3, 6, 8, 8, 8, 2, 3, 5, 5, 7, 7, 9, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99}

local pai = {1, 1, 2, 3, 4, 4, 6, 6, 6, 99, 99, 99, 99, 99, 99, 99, 99}
local start_time = os.clock()
res = CheckIsHu(pai)
local end_time = os.clock()

print(string.format("start_time   : %.9f", start_time))
print(string.format("end_time   : %.9f", end_time))
print(string.format("cost_time  : %.9f", end_time - start_time))
print("能否胡牌：" .. tostring(res))
print("---------测试打印胡牌的组和---------")
PrintTable(remove_attr)

测试结果.png