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
