原创干货！麻将平胡算法

上山打老虎

此算法基本可以通用于所有麻将的平胡规则，即满足m * ABC + n * AAA + AA（其中m、n可为0）的胡牌公式，红黑字牌也可由此算法演变。
首先，我们要约定每张麻将都可以由一个数字表示，比如11表示一万，12表示二万，21表示一条，22表示二条，31表示一筒，32表示二筒……
即所有牌用两位数表示，表示万条筒的两位数个位为牌点，十位为牌类型，其它表示非字牌的两位数与牌类型相同，以下用一个枚举类定义：

import java.util.HashMap;
import java.util.Map;
/**
 * 麻将类型枚举
 *
 * @author zkpursuit
 */
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;
  private CardType(int value, String name) {
    this.value = value;
    this.name = name;
  }
  public int getValue() {
    return value;
  }
  public String getName() {
    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());
    }
  }
  /**
   * 获取牌类型枚举
   *
   * @param typeValue 牌类型值
   * @return 牌类型枚举
   */
  public static final CardType getCardType(int typeValue) {
    return types.get(typeValue);
  }
  /**
   * 获取牌的类型名
   *
   * @param typeValue 牌类型
   * @return 牌类型名
   */
  public static final String getCardTypeName(int typeValue) {
    return typeNames.get(typeValue);
  }
  /**
   * 获取牌类型数值表示
   *
   * @param card 牌号
   * @return 牌类型数值表示
   */
  public static final int getCardTypeValue(int card) {
    if (card < 40) {
      return HandCards.getCardLeftValue(card);
    }
    return card;
  }
  /**
   * 将牌数据转换为现实中可读的牌
   *
   * @param card 牌数据
   * @return 现实中可读的牌
   */
  public static final String getCardName(int card) {
    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) 则为字牌点数。
具体定义一个手牌类，里面定义了各种静态的换算函数，可参看注释。

/**
 * 手牌
 *
 * @author zkpursuit
 */
public class HandCards {
  /**
   * 获取牌号最左边的一位数，如果牌为筒、条、万，则返回值为牌类型数值
   *
   * @param card 牌号
   * @return 牌号从左至右第一位数（十位数）
   */
  public final static int getCardLeftValue(int card) {
    return card / 10;
  }
  /**
   * 获取牌号最右边的一位数，如果牌为筒、条、万，则返回值为牌点数
   *
   * @param card 牌号
   * @return 牌号从右至左第一位数（个位数）
   */
  public final static int getCardRightValue(int card) {
    return card % 10;
  }
  /**
   * 获取牌号最左边的一位数，如果牌为筒、条、万，则返回值为牌类型数值
   *
   * @param idx 牌在归类数组中的索引位置
   * @return 牌号从左至右第一位数（十位数）
   */
  public final static int getCardLeftValueByClusterIndex(int idx) {
    return idx / 10 + 1;
  }
  /**
   * 获取牌号最右边的一位数，如果牌为筒、条、万，则返回值为牌点数
   *
   * @param idx 牌在归类数组中的索引位置
   * @return 牌号从右至左第一位数（个位数）
   */
  public final static int getCardRightValueByClusterIndex(int idx) {
    return idx % 10;
  }
  /**
   * 根据牌号取得其所在的牌归类数组中的索引
   *
   * @param card 牌号
   * @return 牌归类数组中的索引
   */
  public final static int getClusterIndexByCard(int card) {
    int left = getCardLeftValue(card);
    int right = getCardRightValue(card);
    int idx = (left - 1) * 10 + right;
    return idx;
  }
  /**
   * 根据十位数和个位数确定牌在聚合数组中的索引位置
   *
   * @param leftValue 十位数
   * @param rightValue 个位数
   * @return 聚合数组中的索引位置
   */
  public final static int getClusterIndex(int leftValue, int rightValue) {
    return (leftValue - 1) * 10 + rightValue;
  }
  /**
   * 归类牌<br>
   * 数组索引 / 10 + 1 表示牌类型<br>
   * 数组索引 % 10 表示牌点数<br>
   * 数组索引位置的值表示牌数量
   */
  private int[] cardClusterArray;
  /**
   * 起始有效的索引位置<br>
   * 第一个值不为0的索引位置<br>
   */
  private int startIndex;
  /**
   * 归类牌数组的有效索引位置，因为有可能后面的位置全是0<br>
   * 此索引的后续索引位置的值全部为0，即最后一个值不为0的索引位置<br>
   */
  private int lastIndex;
  /**
   * 所有的牌数量
   */
  private int cardTotals;
  /**
   * 构造方法
   */
  public HandCards() {
    cardClusterArray = new int[40];
    startIndex = 1000;
    lastIndex = -1;
    cardTotals = 0;
  }
  /**
   * 构造方法
   *
   * @param cards 未归类的牌数组
   */
  public HandCards(int[] cards) {
    this();
    if (cards != null) {
      setCards(cards);
    }
  }
  /**
   * 重置数据
   */
  public void reset() {
    if (cardTotals != 0) {
      int len = getClusterValidLength();
      for (int i = 0; i < len; i++) {
        cardClusterArray[i] = 0;
      }
    }
    startIndex = 1000;
    lastIndex = -1;
    cardTotals = 0;
  }
  /**
   * 清除数据
   */
  public void clear() {
    reset();
  }
  /**
   * 重置数据并以传入的牌数据再次初始化数据
   *
   * @param cards 牌数据
   */
  public final void setCards(int[] cards) {
    reset();
    for (int card : cards) {
      addCard(card);
    }
  }
  /**
   * 添加num张牌
   *
   * @param card 添加的牌号
   * @param num 添加的数量
   * @return true添加成功；false添加失败
   */
  public boolean addCard(int card, int num) {
    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;
  }
  /**
   * 添加一张牌
   *
   * @param card 牌号
   * @return true添加成功；false添加失败
   */
  public boolean addCard(int card) {
    return addCard(card, 1);
  }
  /**
   * 添加牌集合
   *
   * @param cards 牌集合，比如 [11, 23, 33, 33, 33, 34]
   * @return true添加成功，只要有一张添加失败则全部失败
   */
  public boolean addCards(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张牌
   *
   * @param card 移除的牌号
   * @param num 移除的数量
   * @return true移除成功；false移除失败
   */
  public boolean removeCard(int card, int num) {
    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;
  }
  /**
   * 移除一张牌
   *
   * @param card 牌号
   * @return true移除成功；false移除失败
   */
  public boolean removeCard(int card) {
    return removeCard(card, 1);
  }
  /**
   * 移除牌号对应的所有牌
   *
   * @param card 牌号
   * @return true移除成功；false移除失败
   */
  public boolean removeCardOfAll(int card) {
    int num = getCardNum(card);
    if (num >= 0) {
      return removeCard(card, num);
    }
    return true;
  }
  /**
   * 移除牌
   *
   * @param cards 需要移除的牌
   * @return true表示移除成功，只要有一张牌移除失败则整个失败
   */
  public boolean removeCards(int... cards) {
    for (int card : cards) {
      int idx = getClusterIndexByCard(card);
      if (cardClusterArray[idx] < 1) {
        return false;
      }
    }
    for (int card : cards) {
      removeCard(card);
    }
    return true;
  }
  /**
   * 是否有指定的牌
   *
   * @param card 牌号
   * @return true表示存在
   */
  public boolean hasCard(int card) {
    return getCardNum(card) > 0;
  }
  /**
   * 获取牌号对应的数量
   *
   * @param card 牌号
   * @return 牌号对应的数量
   */
  public int getCardNum(int card) {
    int idx = getClusterIndexByCard(card);
    return cardClusterArray[idx];
  }
  /**
   * 获取归类的牌数据，整除10的索引位置为保留位，不参与任何实际运算<br>
   * 数组索引从0开始，有效长度（后面全部为0）结束<br>
   * 此数组为数据副本，其中的任何数据变动都不会改变原数组<br>
   * 数组索引 / 10 + 1 表示牌类型<br>
   * 数组索引 % 10 表示牌点数<br>
   *
   * @return 归类的牌数据
   */
  public int[] getCardClusterArray() {
    int[] array = new int[getClusterValidLength()];
    System.arraycopy(cardClusterArray, 0, array, 0, array.length);
    return array;
  }
  /**
   * 根据提供的索引位置获取牌数量
   *
   * @param idx 牌归类数组中的索引位置
   * @return 牌数量
   */
  public int getCardNumByClusterIndex(int idx) {
    return cardClusterArray[idx];
  }
  /**
   * 根据索引位置定位对应的牌
   *
   * @param idx 归类牌数组中的索引位置
   * @return -1表示找不到对应的牌，否则返回牌号
   */
  public int getCardByClusterIndex(int idx) {
    if (cardClusterArray[idx] <= 0) {
      return -1;
    }
    int left = getCardLeftValueByClusterIndex(idx);
    int right = getCardRightValueByClusterIndex(idx);
    return left * 10 + right;
  }
  /**
   * 归类牌数组中起始有效索引
   *
   * @return 起始有效索引，第一个值不为0的索引位置
   */
  public int getClusterValidStartIndex() {
    if (cardTotals == 0) {
      return 1;
    }
    return startIndex;
  }
  /**
   * 归类牌数组中最终的有效索引
   *
   * @return 最终有效索引，其后的值全为0
   */
  public int getClusterValidEndIndex() {
    return lastIndex;
  }
  /**
   * 归类牌数组的有效长度<br>
   * 有效的起始索引到有效的最后索引之前的长度<br>
   *
   * @return 有效长度，因为归类数组中后面可能有很多无效的0
   */
  public int getClusterValidLength() {
    return lastIndex + 1;
  }
  /**
   * 所有牌的张数
   *
   * @return 总张数
   */
  public int getCardTotals() {
    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
  public HandCards clone() {
    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;

/**
 *
 * @author zkpursuit
 */
public final class AI {
  /**
   * 递归方式判断平胡
   *
   * @param cardClusterArray 牌号和牌数量的簇集对象集合
   * @param len 所有牌数量
   * @return true表示可以胡牌
   */
  private static boolean isPingHu(int[] cardClusterArray, int startIndex, int len) {
    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;
  }
  /**
   * 递归方式判断平胡
   *
   * @param mycards 手牌
   * @return true表示可以胡牌
   */
  public static boolean isPingHu(HandCards mycards) {
    int[] cardClusterArray = mycards.getCardClusterArray();
    int totals = mycards.getCardTotals();
    if (totals % 3 != 2) {
      return false;
    }
    return AI.isPingHu(cardClusterArray, mycards.getClusterValidStartIndex(), totals);
  }
  public static void main(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);
  }
}