原创干货！麻将平胡算法

此算法基本可以通用于所有麻将的平胡规则，即满足m * ABC + n * AAA + AA（其中m、n可为0）的胡牌公式，红黑字牌也可由此算法演变。

首先，我们要约定每张麻将都可以由一个数字表示，比如11表示一万，12表示二万，21表示一条，22表示二条，31表示一筒，32表示二筒……

即所有牌用两位数表示，表示万条筒的两位数个位为牌点，十位为牌类型，其它表示非字牌的两位数与牌类型相同，以下用一个枚举类定义：

import java.util.HashMap;import java.util.Map;/** * 麻将类型枚举 * *@authorzkpursuit */public enum CardType {

wan(1, "万"), tiao(2, "条"), tong(3, "筒"),

dong(40, "东风"), nan(41, "南风"), xi(42, "西风"),

bei(43, "北风"), zhong(44, "中"), fa(45, "发"), ban(46, "白板");

//类型 private final int value;

//牌名 private final String name;

privateCardType(intvalue, String name){

this.value = value;

this.name = name;

}

publicintgetValue(){

return value;

}

publicStringgetName(){

return name;

}

private static final Map<Integer, String> numMap = new HashMap<>();

private static final Map<Integer, CardType> types = new HashMap<>();

private static final Map<Integer, String> typeNames = new HashMap<>();

static {

numMap.put(1, "一");

numMap.put(2, "二");

numMap.put(3, "三");

numMap.put(4, "四");

numMap.put(5, "五");

numMap.put(6, "六");

numMap.put(7, "七");

numMap.put(8, "八");

numMap.put(9, "九");

CardType[] enums = CardType.values();

for (CardType cardType : enums) {

types.put(cardType.getValue(), cardType);

typeNames.put(cardType.getValue(), cardType.getName());

}

}

/** * 获取牌类型枚举 * *@paramtypeValue 牌类型值 *@return牌类型枚举 */ publicstaticfinalCardTypegetCardType(inttypeValue){

return types.get(typeValue);

}

/** * 获取牌的类型名 * *@paramtypeValue 牌类型 *@return牌类型名 */ publicstaticfinalStringgetCardTypeName(inttypeValue){

return typeNames.get(typeValue);

}

/** * 获取牌类型数值表示 * *@paramcard 牌号 *@return牌类型数值表示 */ publicstaticfinalintgetCardTypeValue(intcard){

if (card < 40) {

return HandCards.getCardLeftValue(card);

}

return card;

}

/** * 将牌数据转换为现实中可读的牌 * *@paramcard 牌数据 *@return现实中可读的牌 */ publicstaticfinalStringgetCardName(intcard){

if (card < 40) {

int type = HandCards.getCardLeftValue(card);

int point = HandCards.getCardRightValue(card);

StringBuilder sb = new StringBuilder();

sb.append(numMap.get(point));

sb.append(getCardTypeName(type));

return sb.toString();

}

return getCardTypeName(card);

}

}

以上定义了各张牌的数字表示，接下来我们分析手牌的存储结构，手牌可以用一个数组表示，数组下标号能除尽10的数组元素为保留位，不用于存储任何数据。举例解释此数组存储牌的数据结构：

0号下标保留位

1~9号下标为万字牌牌点，其对应的数组元素为牌的张数

10号下标保留位

11~19号下标为条字牌牌点，其对应的数组元素为牌的张数

20号下标为保留位

21~29号下标为筒字牌牌点，其对应的数组元素为牌的张数

40~46号下标分别表示东、南、西、北、中、发、白的存储位。

根据以上的定义，则可以根据数组下标获得万条筒字牌的类型和牌点，(下标/10 + 1) 则为字牌类型，(下标%10) 则为字牌点数。

/** * 手牌 * *@authorzkpursuit */public classHandCards{

/** * 获取牌号最左边的一位数，如果牌为筒、条、万，则返回值为牌类型数值 * *@paramcard 牌号 *@return牌号从左至右第一位数（十位数） */ publicfinalstaticintgetCardLeftValue(intcard){

return card / 10;

}

/** * 获取牌号最右边的一位数，如果牌为筒、条、万，则返回值为牌点数 * *@paramcard 牌号 *@return牌号从右至左第一位数（个位数） */ publicfinalstaticintgetCardRightValue(intcard){

return card % 10;

}

/** * 获取牌号最左边的一位数，如果牌为筒、条、万，则返回值为牌类型数值 * *@paramidx 牌在归类数组中的索引位置 *@return牌号从左至右第一位数（十位数） */ publicfinalstaticintgetCardLeftValueByClusterIndex(intidx){

return idx / 10 + 1;

}

/** * 获取牌号最右边的一位数，如果牌为筒、条、万，则返回值为牌点数 * *@paramidx 牌在归类数组中的索引位置 *@return牌号从右至左第一位数（个位数） */ publicfinalstaticintgetCardRightValueByClusterIndex(intidx){

return idx % 10;

}

/** * 根据牌号取得其所在的牌归类数组中的索引 * *@paramcard 牌号 *@return牌归类数组中的索引 */ publicfinalstaticintgetClusterIndexByCard(intcard){

int left = getCardLeftValue(card);

int right = getCardRightValue(card);

int idx = (left - 1) * 10 + right;

return idx;

}

/** * 根据十位数和个位数确定牌在聚合数组中的索引位置 * *@paramleftValue 十位数 *@paramrightValue 个位数 *@return聚合数组中的索引位置 */ publicfinalstaticintgetClusterIndex(intleftValue,intrightValue){

return (leftValue - 1) * 10 + rightValue;

}

/**

* 归类牌 

* 数组索引 / 10 + 1 表示牌类型 

* 数组索引 % 10 表示牌点数 

* 数组索引位置的值表示牌数量

*/ private int[] cardClusterArray;

/**

* 起始有效的索引位置 

* 第一个值不为0的索引位置 

*/ private int startIndex;

/**

* 归类牌数组的有效索引位置，因为有可能后面的位置全是0 

* 此索引的后续索引位置的值全部为0，即最后一个值不为0的索引位置 

*/ private int lastIndex;

/**

* 所有的牌数量

*/ private int cardTotals;

/**

* 构造方法

*/ publicHandCards(){

cardClusterArray = new int[40];

startIndex = 1000;

lastIndex = -1;

cardTotals = 0;

}

/** * 构造方法 * *@paramcards 未归类的牌数组 */ publicHandCards(int[] cards){

this();

if (cards != null) {

setCards(cards);

}

}

/**

* 重置数据

*/ publicvoidreset(){

if (cardTotals != 0) {

int len = getClusterValidLength();

for (int i = 0; i < len; i++) {

cardClusterArray[i] = 0;

}

}

startIndex = 1000;

lastIndex = -1;

cardTotals = 0;

}

/**

* 清除数据

*/ publicvoidclear(){

reset();

}

/** * 重置数据并以传入的牌数据再次初始化数据 * *@paramcards 牌数据 */ publicfinalvoidsetCards(int[] cards){

reset();

for (int card : cards) {

addCard(card);

}

}

/** * 添加num张牌 * *@paramcard 添加的牌号 *@paramnum 添加的数量 *@returntrue添加成功；false添加失败 */ publicbooleanaddCard(intcard,intnum){

int idx = getClusterIndexByCard(card);

int lastNum = cardClusterArray[idx] + num;

if (lastNum > 4) {

return false;

}

cardClusterArray[idx] = lastNum;

if (idx > lastIndex) {

lastIndex = idx;

}

if (idx < startIndex) {

startIndex = idx;

}

cardTotals += num;

return true;

}

/** * 添加一张牌 * *@paramcard 牌号 *@returntrue添加成功；false添加失败 */ publicbooleanaddCard(intcard){

return addCard(card, 1);

}

/** * 添加牌集合 * *@paramcards 牌集合，比如 [11, 23, 33, 33, 33, 34] *@returntrue添加成功，只要有一张添加失败则全部失败 */ publicbooleanaddCards(int... cards){

for (int card : cards) {

int idx = getClusterIndexByCard(card);

int lastNum = cardClusterArray[idx] + 1;

if (lastNum > 4) {

return false;

}

}

for (int card : cards) {

addCard(card);

}

return true;

}

/** * 移除num张牌 * *@paramcard 移除的牌号 *@paramnum 移除的数量 *@returntrue移除成功；false移除失败 */ publicbooleanremoveCard(intcard,intnum){

int idx = getClusterIndexByCard(card);

if (cardClusterArray[idx] < num) {

return false;

}

cardClusterArray[idx] -= num;

if (cardClusterArray[idx] == 0) {

if (idx == startIndex) {

startIndex = 1000;

for (int i = idx; i < cardClusterArray.length; i++) {

if (cardClusterArray[i] > 0) {

startIndex = i;

break;

}

}

}

if (lastIndex == idx) {

int start = startIndex;

if (start >= cardClusterArray.length) {

start = 0;

}

lastIndex = -1;

for (int i = idx; i >= start; i--) {

if (cardClusterArray[i] > 0) {

lastIndex = i;

break;

}

}

}

}

cardTotals -= num;

return true;

}

/** * 移除一张牌 * *@paramcard 牌号 *@returntrue移除成功；false移除失败 */ publicbooleanremoveCard(intcard){

return removeCard(card, 1);

}

/** * 移除牌号对应的所有牌 * *@paramcard 牌号 *@returntrue移除成功；false移除失败 */ publicbooleanremoveCardOfAll(intcard){

int num = getCardNum(card);

if (num >= 0) {

return removeCard(card, num);

}

return true;

}

/** * 移除牌 * *@paramcards 需要移除的牌 *@returntrue表示移除成功，只要有一张牌移除失败则整个失败 */ publicbooleanremoveCards(int... cards){

for (int card : cards) {

int idx = getClusterIndexByCard(card);

if (cardClusterArray[idx] < 1) {

return false;

}

}

for (int card : cards) {

removeCard(card);

}

return true;

}

/** * 是否有指定的牌 * *@paramcard 牌号 *@returntrue表示存在 */ publicbooleanhasCard(intcard){

return getCardNum(card) > 0;

}

/** * 获取牌号对应的数量 * *@paramcard 牌号 *@return牌号对应的数量 */ publicintgetCardNum(intcard){

int idx = getClusterIndexByCard(card);

return cardClusterArray[idx];

}

/** * 获取归类的牌数据，整除10的索引位置为保留位，不参与任何实际运算
* 数组索引从0开始，有效长度（后面全部为0）结束
* 此数组为数据副本，其中的任何数据变动都不会改变原数组
* 数组索引 / 10 + 1 表示牌类型
* 数组索引 % 10 表示牌点数
* *@return归类的牌数据 */ public int[] getCardClusterArray() {

int[] array = new int[getClusterValidLength()];

System.arraycopy(cardClusterArray, 0, array, 0, array.length);

return array;

}

/** * 根据提供的索引位置获取牌数量 * *@paramidx 牌归类数组中的索引位置 *@return牌数量 */ publicintgetCardNumByClusterIndex(intidx){

return cardClusterArray[idx];

}

/** * 根据索引位置定位对应的牌 * *@paramidx 归类牌数组中的索引位置 *@return-1表示找不到对应的牌，否则返回牌号 */ publicintgetCardByClusterIndex(intidx){

if (cardClusterArray[idx] <= 0) {

return -1;

}

int left = getCardLeftValueByClusterIndex(idx);

int right = getCardRightValueByClusterIndex(idx);

return left * 10 + right;

}

/** * 归类牌数组中起始有效索引 * *@return起始有效索引，第一个值不为0的索引位置 */ publicintgetClusterValidStartIndex(){

if (cardTotals == 0) {

return 1;

}

return startIndex;

}

/** * 归类牌数组中最终的有效索引 * *@return最终有效索引，其后的值全为0 */ publicintgetClusterValidEndIndex(){

return lastIndex;

}

/** * 归类牌数组的有效长度
* 有效的起始索引到有效的最后索引之前的长度
* *@return有效长度，因为归类数组中后面可能有很多无效的0 */ publicintgetClusterValidLength(){

return lastIndex + 1;

}

/** * 所有牌的张数 * *@return总张数 */ publicintgetCardTotals(){

return cardTotals;

}

/** * 获取所有的牌数据，未归类 * *@return未归类的牌数据，两位数的牌号数组 */ public int[] getCards() {

if (cardTotals <= 0) {

return null;

}

int len = getClusterValidLength();

int[] cards = new int[cardTotals];

int idx = 0;

for (int i = getClusterValidStartIndex(); i < len; i++) {

int left = getCardLeftValueByClusterIndex(i);

int right = getCardRightValueByClusterIndex(i);

int count = cardClusterArray[i];

int card = left * 10 + right;

for (int j = 0; j < count; j++) {

cards[idx] = card;

idx++;

}

}

return cards;

}

@Override publicHandCardsclone(){

HandCards copy = new HandCards();

copy.cardTotals = this.cardTotals;

copy.lastIndex = this.lastIndex;

copy.startIndex = this.startIndex;

if (cardClusterArray != null) {

int[] copyCardClusterArray = new int[cardClusterArray.length];

System.arraycopy(cardClusterArray, 0, copyCardClusterArray, 0, cardClusterArray.length);

copy.cardClusterArray = copyCardClusterArray;

}

return copy;

}

}

准备工作都做好了，怎么使用上面定义的数据结构实现平胡算法呢？平胡满足m * ABC + n * AAA + AA（其中m、n可为0）的胡牌公式，分析此公式，AA表示一对牌，则算法必然需要分析手牌中是否含有一对牌，ABC表示三张相同类型且连续的牌，AAA表示三张相同类型且牌点也相同的牌。

依据公式，我们用递归思路编写一个平胡胡牌算法（其中包含简单的测试用例）：

import java.util.Arrays;/** * *@authorzkpursuit */public final classAI{

/** * 递归方式判断平胡 * *@paramcardClusterArray 牌号和牌数量的簇集对象集合 *@paramlen 所有牌数量 *@returntrue表示可以胡牌 */ privatestaticbooleanisPingHu(int[] cardClusterArray,intstartIndex,intlen){

if (len == 0) {

return true;

}

int i;

if (len % 3 == 2) {

//移除一对（两张牌），胡牌中必须包含一对 for (i = startIndex; i < cardClusterArray.length; i++) {

if (cardClusterArray[i] >= 2) {

cardClusterArray[i] -= 2;

if (AI.isPingHu(cardClusterArray, startIndex, len - 2)) {

return true;

}

cardClusterArray[i] += 2;

}

}

} else {

//是否是顺子 int loopCount = cardClusterArray.length - 2;

for (i = startIndex; i < loopCount; i++) {

int idx1 = i + 1;

int idx2 = i + 2;

int type1 = HandCards.getCardLeftValueByClusterIndex(i);

int type2 = HandCards.getCardLeftValueByClusterIndex(idx1);

int type3 = HandCards.getCardLeftValueByClusterIndex(idx2);

if (cardClusterArray[i] > 0 && cardClusterArray[idx1] > 0 && cardClusterArray[idx2] > 0 && type1 < 4 && type2 < 4 && type3 < 4) {

cardClusterArray[i] -= 1;

cardClusterArray[idx1] -= 1;

cardClusterArray[idx2] -= 1;

if (AI.isPingHu(cardClusterArray, startIndex, len - 3)) {

return true;

}

cardClusterArray[i] += 1;

cardClusterArray[idx1] += 1;

cardClusterArray[idx2] += 1;

}

}

//三个一样的牌（暗刻） for (i = startIndex; i < cardClusterArray.length; i++) {

if (cardClusterArray[i] >= 3) {

cardClusterArray[i] -= 3;

if (AI.isPingHu(cardClusterArray, startIndex, len - 3)) {

return true;

}

cardClusterArray[i] += 3;

}

}

}

return false;

}

/** * 递归方式判断平胡 * *@parammycards 手牌 *@returntrue表示可以胡牌 */ publicstaticbooleanisPingHu(HandCards mycards){

int[] cardClusterArray = mycards.getCardClusterArray();

int totals = mycards.getCardTotals();

if (totals % 3 != 2) {

return false;

}

return AI.isPingHu(cardClusterArray, mycards.getClusterValidStartIndex(), totals);

}

publicstaticvoidmain(String[] args){

HandCards handCards = new HandCards(new int[]{11, 12, 13, 22, 23, 24, 33, 33, 33, 36, 36});

System.out.println(Arrays.toString(handCards.getCardClusterArray()));

System.out.println(Arrays.toString(handCards.getCards()));

for (int i = handCards.getClusterValidStartIndex(); i <= handCards.getClusterValidEndIndex(); i++) {

int card = handCards.getCardByClusterIndex(i);

if (card > 0) {

int num = handCards.getCardNum(card);

System.out.println(num + "张 " + CardType.getCardName(card));

}

}

boolean bool = isPingHu(handCards);

System.out.println("是否胡牌：" + bool);

}

}

觉得不错请点赞支持，欢迎留言或进我的个人群855801563领取【架构资料专题目合集90期】、【BATJTMD大厂JAVA面试真题1000+】，本群专用于学习交流技术、分享面试机会，拒绝广告，我也会在群内不定期答题、探讨。

原创干货！麻将平胡算法

推荐阅读更多精彩内容