[算法] 麻将序数牌组合方案

系统管理员 2022-06-06 08:45 145阅读 0赞

// 环境: centos7.2, g++ v4.8.5
    
    #include <iostream>
    #include <unistd.h>
    #include <stdio.h>
    #include <string.h>
    #include <vector>
    #include <map>
    
    using namespace std;
    
    enum CombineType
    {
    	CombineType_Null = 0,	// 单牌
    	CombineType_Dui = 1,	// 对子
    	CombineType_Ke = 2,		// 刻
    	CombineType_Shun = 3	// 顺子
    };
    
    struct Combine				// 一种组合
    {
    	CombineType		type;
    	vector<int>		cards;
    
    	Combine()
    	{
    		type = CombineType_Null;
    	}
    };
    
    map<int, vector<int>> classify(vector<int>& v)
    {
    	map<int, vector<int>> m;
    	for(auto& it : v)
    	{
    		if(m.find(it) == m.end())
    		{
    			m[it] = {};
    		}
    		m[it].push_back(it);
    	}
    
    #if 1
    	for(auto& it : m)
    	{
    		printf("%d: ", it.first);
    		for(auto& it2 : it.second)
    			printf("%d ", it2);
    		printf("\n");
    	}
    #endif
    
    	return m;
    }
    
    // 从m中找一种符合组合类型为type的组合, 这个组合里最小的卡id为min
    Combine findCombine(map<int, vector<int>>& m, int min, CombineType type)
    {
    	printf("开始查找: min=%d, type=%d\n", min, type);
    
    	Combine comb;
    	if(type == CombineType_Dui || type == CombineType_Ke)	// 查找对子或刻
    	{
    		uint n = type == CombineType_Dui ? 2 : 3;
    		if(m[min].size() >= n)						// 能找到对子或刻
    		{
    			for(int i = 0; i < n; i++)				// 从m[min]中取n张卡到comb.cards中
    			{
    				comb.cards.push_back(min);
    				m[min].pop_back();
    				if(m[min].empty())
    					m.erase(min);
    			}
    			comb.type = type;
    		}
    	}
    	else if(type == CombineType_Shun && min <= 7)	// 8往后不可能组成顺子了
    	{
    		if(m.find(min) != m.end() && m.find(min+1) != m.end() && m.find(min+2) != m.end())	// 找到以min开始的顺子
    		{
    			comb.cards = {min, min+1, min+2};
    			comb.type = type;
    
    			for(auto& it : comb.cards)
    			{
    				m[it].pop_back();
    				if(m[it].empty())
    					m.erase(it);
    			}
    		}
    	}
    
    	return comb;	
    }
    
    void display(Combine comb)
    {
    	printf("comb.type = %d, cards = ", comb.type);
    	for(auto& it : comb.cards)
    		printf("%d ", it);
    	printf("\n\n");
    }
    
    void displayCombines(vector<Combine>& v)
    {
    	for(auto& it : v)
    	{
    		for(auto& it2 : it.cards)
    		{
    			printf(" %d", it2);
    		}
    		printf(",");
    	}
    	printf("\n\n");
    }
    
    // vector<Combine>:			一种组合方案
    // vector<vector<Combine>>:	多种组合方案
    vector<vector<Combine>> getCombines(vector<int>& v)
    {
    	vector<vector<Combine>> ret;
    
    	auto m = classify(v);
    
    	auto firstCard = [&m]()						// 查找m中键最小的那个数
    	{
    		for(auto& it : m)
    		{
    			return it.first;
    		}
    		return 0;
    	};
    
    	auto useCombine = [&m](Combine& comb)		// 使用组合
    	{
    		for(auto& it : comb.cards)				// 从m中删除comb中的卡牌
    		{
    			m[it].pop_back();
    			if(m[it].empty())
    				m.erase(it);
    		}
    	};
    
    	auto recyle = [&m](Combine& comb)			// 回收comb中的卡牌
    	{
    		for(auto& it : comb.cards)
    		{
    			if(m.find(it) == m.end())
    			{
    				m[it] = {};
    			}
    			m[it].push_back(it);
    		}
    	};
    
    	printf("\n开始查找新的组合方案-----------------\n");
    	vector<Combine> stack;
    	int min = firstCard();
    	CombineType oldType = CombineType_Null;		// 下次从此类型之后开始找
    	do
    	{
    		bool b = false;
    		auto types = {CombineType_Dui, CombineType_Ke, CombineType_Shun};
    		for(auto& it : types)
    		{
    			if(it <= oldType)					// 以前找过的组合类型, 不再继续寻找
    				continue;
    
    			auto comb = findCombine(m, min, it);
    			if(comb.type == it)					// 找到一个组合
    			{
    				stack.push_back(comb);
    				b = true;
    				break;
    			}
    		}
    		if(b)						
    		{
    			printf("找到一个组合: ");
    			display(stack.back());
    
    			if(m.empty())						// 找到一种组合方案(牌分配完了)
    			{
    				ret.push_back(stack);
    				printf("【找到一种组合方案】:");
    				displayCombines(stack);
    			}
    			else
    			{
    				auto tmp = min;
    				min = firstCard();				// 确定下次要找的牌
    				if(tmp != min)
    					oldType = CombineType_Null;	// 下次查找的类型重置
    			}
    		}
    		else if(!stack.empty())					// 有可回收的组合(回归查找准备)		
    		{
    			auto comb = stack.back();			// 取(复制)栈顶元素
    			oldType = comb.type;				// 记录上次此组合开始查找的类型
    			min = comb.cards[0];				// 下次从此牌开始找
    
    			printf("回收一个组合: ");
    			display(comb);
    
    			recyle(comb);						// 回收栈顶元素中的卡牌
    			stack.pop_back();					// 弹出栈顶组合
    		}
    		else									// 没有可回收的组合(即方案寻找结束)
    			break;
    
    	}while(true);
    
    	return ret;
    }
    
    int main()
    {
    	//vector<int> v = {1, 1, 1, 2, 2, 2, 8, 8};
    	vector<int> v = {1, 1, 2, 4, 5, 6};
    	auto vvc = getCombines(v);
    
    	printf("--------------------------------\n");
    	printf("vvc.size=%d\n", vvc.size());
    	for(auto& vc : vvc)
    	{
    		for(auto& comb : vc)
    		{
    			printf("%d: ", comb.type);
    			for(auto& c : comb.cards)
    				printf("%d ", c);
    			printf("\n");
    		}
    		printf("\n");
    	}
    
    	return 0;
    }

以上代码是模拟麻将的序数牌，如万、筒、条，将同是万字的牌按对子、刻、顺子去组合, 列出所有可能的组合！