纸牌游戏：计算最小出牌次数（C#）

1、实现方式

C#递归计算每组牌型的对应组合，取最小组合数 注意定义：一组牌型意为单张、对子、三张、顺子、连对、炸弹（四张）等；顺子三连起，对子三连起

2、实现思路

不考虑花色，将数据量压缩即去重，要获取全部不重复组合：3445566688 =》34568 =》3456、345、456、3、4、5、6、8加入重复值计算更多组合：3445566688 =》445566、44、55、66、88、666由于组合数较多，计算量太大（1组计算1次，2组计算2次，3组计算4次，4组计算8次，…n组计算2^n-1次，如下图），先把单张的组合剔除，根据张数进行从大到小的排序，即我们现在要计算的组合有：445566、3456、345、456、666、44、55、66、88 这几组。下图中，最好是在前面的几条路中走通，越前面的路表示出牌手数越少，比如{1,2,3} 中的三个组合能组成一个列表，那就表示该列表只要三次就能出完，但是如果走最后一条路时，说明列表中只有组合3这个非单张组合，那么就表示这个列表是比较乱的，而且出牌次数会比较多，因为除了组合3以外，都是需要单张单张的出。最后通过递归计算获取全部的组合列表（如果组合数量较大，我们不可能计算全部的组合的，后面会讲）

3、牌型定义

//牌值定义 public enum TPokerValue { uEmpty = 0, u3 = 3, u4 = 4, u5 = 5, u6 = 6, u7 = 7, u8 = 8, u9 = 9, uT = 10, uJ = 11, uQ = 12, uK = 13, uA = 14, u2 = 15, uSize = 16, }; //组合定义 public struct TMeldRecord { public int straightCount; //连续次数 public TPokerValue startValue; //起始值 public int multiple; //重复倍数 public override string ToString() { return string.Format("startValue:{0} straightCount:{1} multiple:{2}", startValue, straightCount, multiple); } }

4、获取全部组合（不含重复）

public void Calc(string pokerData) { Debug.Log("测试数据："); Debug.Log(pokerData); string log = ""; //获取数量数组 int[] countArray = GetCountArray(pokerData); //打印数量 foreach (var item in countArray) log = string.Format("{0},{1}", log, item); Debug.Log(log); Debug.Log("获取不含重复值的组合"); //获取不重复的组合 List<TMeldRecord> noRepeatMelds = GetAllMeldRecords(countArray); //打印数据 foreach (var item in noRepeatMelds) Debug.Log(item); } //获取牌的数量数组 private int[] GetCountArray(string str) { if (str == null || str.Length == 0) { Debug.LogError("str == null || str.Length == 0"); return null; } str = str.ToUpper(); int[] pokersCount = new int[(int)TPokerValue.uSize]; for (int i = 0; i < str.Length; i++) { int value = 0; switch (str[i]) { case 'T': value = 10; break; case 'J': value = 11; break; case 'Q': value = 12; break; case 'K': value = 13; break; default: value = str[i] - '0'; if (value < 0 || value > 9) { Debug.LogError("字符串错误:" + str[i]); return null; } break; } pokersCount[value]++; if (pokersCount[value] > 4) { Debug.LogError("数量超过四个:" + str[i]); return null; } } return pokersCount; } public List<TMeldRecord> GetAllMeldRecords(int[] countArray) { List<TMeldRecord> pokerRecords = new List<TMeldRecord>(); //获取全部的顺子 pokerRecords.AddRange(GetAllStraights(countArray)); //获取全部的单张 pokerRecords.AddRange(GetAllSingles(countArray)); return pokerRecords; } private List<TMeldRecord> GetAllSingles(int[] pokerCountArray) { List<TMeldRecord> records = new List<TMeldRecord>(); for (TPokerValue curValue = 0; curValue <= TPokerValue.u2; curValue++) { if (pokerCountArray[(int)curValue] > 0) { records.Add(new TMeldRecord() { startValue = curValue, straightCount = 1, multiple = 1 }); } } return records; } private List<TMeldRecord> GetAllStraights(int[] pokerCountArray, int minStraightCount = 3) { List<TMeldRecord> records = new List<TMeldRecord>(); int straightCount = 0; for (TPokerValue curValue = TPokerValue.u3; curValue <= TPokerValue.u2; curValue++) { if (pokerCountArray[(int)curValue] > 0 && curValue != TPokerValue.u2) { straightCount++; if (straightCount >= minStraightCount) { records.Add(new TMeldRecord() { straightCount = straightCount, startValue = curValue - straightCount + 1, multiple = 1 }); } } else { //当该值不存在时，回归原始，带自加后，判断下一层及 curValue = curValue - straightCount; straightCount = 0; } } return records; }

执行Calc方法

5、加入重复值，获取剩余组合

public void Calc(string pokerData) { .......看第4小节....... Debug.Log("获取含重复值的组合"); List<TMeldRecord> combinedRecords = CombineMelds(noRepeatMelds, countArray); foreach (var item in combinedRecords) Debug.Log(item); } public List<TMeldRecord> CombineMelds(List<TMeldRecord> recordList, int[] pokerCountArray) { List<TMeldRecord> combinedRecords = new List<TMeldRecord>(); for (int i = 0; i < recordList.Count; i++) { TMeldRecord record = recordList[i]; if (record.straightCount == 1) { int count = pokerCountArray[(int)record.startValue]; for (int curCount = 2; curCount <= count; curCount++) { combinedRecords.Add(new TMeldRecord() { multiple = curCount, startValue = record.startValue, straightCount = record.straightCount }); } } else if (record.straightCount >= 3) { int targetMultiple = 2; //判断是否存在三（或更多）连对 for (int j = 0; j < record.straightCount; j++) { TPokerValue curValue = record.startValue + j; int count = pokerCountArray[(int)curValue]; if (count < targetMultiple) { targetMultiple = count; break; } } if (targetMultiple != record.multiple) { combinedRecords.Add(new TMeldRecord() { multiple = targetMultiple, startValue = record.startValue, straightCount = record.straightCount }); } } else Debug.LogError("ERROR MeldRecord:" + record.ToString()); } return combinedRecords; }

执行结果：

6、计算最小手数

public void Calc(string pokerData) { .......看第5小节....... Debug.Log("全部的组合"); List<TMeldRecord> allRecords = new List<TMeldRecord>(); allRecords.AddRange(noRepeatMelds); allRecords.AddRange(combinedRecords); foreach (var item in allRecords) Debug.Log(item); //单张去除 List<TMeldRecord> allRecordsTmp = allRecords.FindAll((x) => { return !IsSingle(x); }); //从多到少，从小到排序 allRecordsTmp.Sort((x, y) => { if (y.straightCount == x.straightCount) return x.startValue - y.startValue; return y.straightCount - x.straightCount; }); Debug.Log("参与计算的组合"); foreach (var item in allRecordsTmp) Debug.Log(item); } //判断牌型是否是单张 public bool IsSingle(TMeldRecord record) { return record.multiple == 1 && record.straightCount == 1; }

执行结果：

public void Calc(string pokerData) { .....加上上面的..... TMeldRecord[][] resultMelds = CalcMinMeldsCount(allRecordsTmp, countArray); Debug.Log("总共获取到了" + resultMelds.Length + " 副手牌"); foreach (var meldsItem in resultMelds) { int count = 0; foreach (var item in meldsItem) count += item.straightCount * item.multiple; Debug.Log("************** 最小手数:" + (meldsItem.Length + pokerData.Length - count) + " 单牌数：" + (pokerData.Length - count)); foreach (var item in meldsItem) Debug.Log(item); } } /// <summary> /// 该方法用于 排序全部的组合，并获得排列中最短的那些排列 /// 返回值用数组，是因为 存在 最小手数相同的多个组合 /// </summary> /// <param name="allRecords">组合内容</param> /// <param name="countArray">每张牌的数量</param> /// <returns></returns> public static TMeldRecord[][] CalcMinMeldsCount(List<TMeldRecord> allRecords, int[] countArray) { //每次获取，需要重置 safeIndex = 5000; List<IntegerList> minRecords = new List<IntegerList>(); int minMeldCount = int.MaxValue; CalcSelfLoop(0, ref minMeldCount, countArray, allRecords, new IntegerList(), minRecords); TMeldRecord[][] meldRecords = new TMeldRecord[minRecords.Count][]; for (int i = 0; i < minRecords.Count; i++) { meldRecords[i] = new TMeldRecord[minRecords[i].Count]; int meldIdx = 0; for (int j = 0; j < allRecords.Count; j++) { if (minRecords[i].Contain(j)) { meldRecords[i][meldIdx++] = allRecords[j]; } } } return meldRecords; } //防止计算量过大，造成客户端严重卡顿，故设定一个数量，只能访问该方法指定次数，到达指定次数，返回相应结果 private static int safeIndex = 5000; public static void CalcSelfLoop(int currentIndex, ref int minMeldCount, int[] countArray, List<TMeldRecord> allRecords, IntegerList cacheRecords, List<IntegerList> resultRecords) { if (safeIndex-- <= 0) { if (safeIndex == -1) Debug.Log("超过预期计算量，为防止卡顿，开始强制结束"); return; } //遍历完毕 if (currentIndex >= allRecords.Count) { //判断结束，缓存数据 resultRecords.Add(cacheRecords); return; } //判断剩余各个组合是否可以 组合在一起 for (int i = currentIndex; i < allRecords.Count; i++) { TMeldRecord curRecord = allRecords[currentIndex]; //每局开始之前，另存一份剩余数量，以防被别的组合修改 int[] restArrayCount = new int[countArray.Length]; Array.Copy(countArray, restArrayCount, countArray.Length); //组合也复制一份，防止被修改 IntegerList cacheRecordNew = cacheRecords; //判断剩余数量是否足够 bool isEnough = true; for (int tmpIdx = 0; tmpIdx < curRecord.straightCount; tmpIdx++) { if (restArrayCount[(int)curRecord.startValue + tmpIdx] < curRecord.multiple) { isEnough = false; break; } } if (isEnough) { //足够，则减去相应数量 for (int tmpIdx = 0; tmpIdx < curRecord.straightCount; tmpIdx++) { restArrayCount[(int)curRecord.startValue + tmpIdx] -= curRecord.multiple; } //保存该组合索引 cacheRecordNew.Add(currentIndex); } //对下一组合进行判断 CalcSelfLoop(++currentIndex, ref minMeldCount, restArrayCount, allRecords, cacheRecordNew, resultRecords); } }

执行结果（篇幅有限，只截取了最上面的日志和最下面的日志）： 现在获取到了256幅手牌列表，中间就包含了 最小出牌次数的列表，现在就需要在获取的时候加入判断，如果比我已获取到的最大手数大的话，就舍弃前面全部获取到的，目的就是只保存出牌手数最少的那些列表。 上面我们看到了有大量重复的列表，我们也需要剔除，剔除方式：判断全部的索引值是否相同，有一个技巧就是用到 这两个运算符‘|’和‘&’加快计算效率。看上面代码，可以知道有个 IntegerList 类，我没有发源码出来，其实这是一个结构体，而且是一个只保存整型的结构体，在这个结构体中，保存了一个列表全部的组合索引值。 这个结构体的最大值是long（最大值为2⁶³）型，通过2^索引值，进行保存，所以如索引值达到了63（组合数达到64），就会超过long的最大值，所以只要牌的张数不是太多，long大部分时候是满足需求的，如果确实组合数超过了64，那么就要把IntegerList换成别的方式了。

public struct IntegerList { private long _allValue; private const int Base = 2; public int Count { get; private set; } public void Add(int value) { Count++; _allValue |= getValue(value); } public bool Contain(int value) { return (_allValue & getValue(value)) == getValue(value); } private long getValue(int value) { return (long)Math.Pow(Base, value); } public long Value { get { return _allValue; } } }

只保存最小组合数 和 去除重复的组合数的方式如下：

public static void CalcSelfLoop(int currentIndex, ref int minMeldCount, int[] countArray, List<TMeldRecord> allRecords, IntegerList cacheRecords, List<IntegerList> resultRecords) { ......忽略上面.... //遍历完毕 if (currentIndex >= allRecords.Count) { //该组合列表中剩余单张数量 int curSingleCount = GetTotalCount(countArray); if (minMeldCount >= curSingleCount + cacheRecords.Count) { //如果当前的组合数小于前面的组合的最小的组合数，则情况前面的组合数 if (curSingleCount + cacheRecords.Count < minMeldCount) resultRecords.Clear(); minMeldCount = curSingleCount + cacheRecords.Count; //重复组合 不加入列表 for (int i = 0; i < resultRecords.Count; i++) { if (cacheRecords.Value == resultRecords[i].Value) return; } //判断结束，缓存数据 resultRecords.Add(cacheRecords); } return; } .....忽略下面..... } public static int GetTotalCount(int[] countArray) { if (countArray == null) return 0; int result = 0; for (int i = 0; i < countArray.Length; i++) result += countArray[i]; return result; }

执行结果： 现在就职剩下了3副手牌了，且最小手数都是4，也就是说3445566688的最小出牌手数列表有：

3456、456、88，外加单张6345、456、66、88445566、88，外加单张3、6

PS：上面有个safeIndex，这里需要讲一下，当组合太多时，全部计算完不太现实，也没必要，因为手数最少的都是在前面，后面留下的都是单张了， 所以safeIndex就是为了避免计算太多而导致的卡顿而设计的，目前设定为5000，用一台i7 CPU的笔记本，递归五千次 是需要30ms左右，基本不会卡顿。