快速生成唯一整数
本文关键字:唯一 整数 | 更新日期: 2023-09-27 18:16:12
背景
我正在写一个Cribbage统计计算器。起初,我让它计算每一只可能的5张牌手的点值,并将其与维基百科进行核对,直到我的数字与他们的数字相同。
现在我正在计算每一对可能的双手(你的手和婴儿床(,大约2.3万亿的组合,所以优化是关键。
代码
所有卡片的编号都在0到51之间。Hand
构造函数采用长度为5的int[]
,并假定最后一张卡是起始卡。现在所有的点数计算代码都处理好了,我想优化手牌号码的生成过程。
现在我有:
private static IEnumerable<Tuple<int[], int[]>> GetTwoHands()
{
bool[] avail = new bool[52];
for (int i = 0; i < 52; i++)
{
avail[i] = true;
}
// hand 1 cards
for (int i = 0; i < 52; i++)
{
avail[i] = false;
for (int j = i + 1; j < 52; j++)
{
avail[j] = false;
for (int k = j + 1; k < 52; k++)
{
avail[k] = false;
for (int l = k + 1; l < 52; l++)
{
avail[l] = false;
// hand 2 (crib) cards
for (int i2 = 0; i2 < 52; i2++)
{
if (!avail[i2])
{
continue;
}
avail[i2] = false;
for (int j2 = i2 + 1; j2 < 52; j2++)
{
if (!avail[j2])
{
continue;
}
avail[j2] = false;
for (int k2 = j2 + 1; k2 < 52; k2++)
{
if (!avail[k2])
{
continue;
}
avail[k2] = false;
for (int l2 = k2 + 1; l2 < 52; l2++)
{
if (!avail[l2])
{
continue;
}
avail[l2] = false;
// shared starter card
for (int m = 0; m < 52; m++)
{
if (!avail[m])
{
continue;
}
yield return Tuple.Create(new int[] { i, j, k, l, m }, new int[] { i2, j2, k2, l2, m });
}
avail[l2] = true;
}
avail[k2] = true;
}
avail[j2] = true;
}
avail[i2] = true;
}
avail[l] = true;
}
avail[k] = true;
}
avail[j] = true;
}
avail[i] = true;
}
}
其中i
到l
是第一手的卡号,i2
到l2
是第二手的卡号并且m
是起始卡的卡号。显然,手上不可能有重复的牌,所以对于第二手牌,我确保每个卡号都不在手1中。
我使用C#的IEnumerable<T>.AsParallel().ForAll(action)
来利用我所有的处理器核心,所以Hand(int[])
发生在操作中,而不是同步的GetTwoHands()
。
问题
- 有没有一种方法可以在不牺牲性能的情况下清理所有这些循环?我怀疑,尽管还没有测试,递归会因为所有的函数调用而减慢速度
- 有没有更快的算法来生成这些数字
我这么晚才上场,但由于我从7岁起就开始玩Cribbage(我52岁了(,我可能会帮上一点忙。
在其他帖子中似乎有递归的暗示。当你谈论大数字时,你不妨反复思考,并具有战略性。
我知道发布URI是禁止的,但是。。。这会节省很多时间。
如果你在这里:http://www.cribbagematch.com/,你会发现Tim Schempp从2000年创建的Cribbage包中重新启动了Royal Crib,目前正在测试中。有一个电子邮件地址可以联系到他。前几天我和他聊过,他说当他做出改变时,他会用ca.1k游戏重新测试他的代码。
长话短说,他(在2000年(整理了几份文件,为你正在考虑生成的统计数据以及他在2000年使用的底层算法提供了很多见解。只要准备好看很多sigma。两个PDF文档每个大约有40多页。问他要一份,因为他已经分享了很多年了。他的一些工作持续了好几天(记住,这是14年前的事了(。
如果你想玩的数字与所提供的信息不符,那么有足够的信息向你展示如何进行一些自己的特殊计算。例如,一个球员的4码手,在投球后,可以像这样分解:
- 4张不同的卡片。。。。。。。。。。。。。。。。715
- 1对,2个不同。。。。。。。。。。。。。。858
- 2对。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。78
- 3种,1种差异…………156
-
4种。。。。。。。。。。。。。。。。。。。。。。13
-
总计。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。1'820总组合
那么,为什么暴力和过滤器重复?
例如,在玩家对玩家的游戏中,有18’395张六张牌的组合(一名玩家(,3’274’375张四张卡的组合。Tim指出,the Play(4x4(的组合数量在1’820平方的1%以内。
我想,如果你在方法论上更有策略性,你会发现只有不到2.3T的独特序列:你在考虑处理同花顺吗?如果没有,那么你不需要担心52张牌,只有13张,有4次出现。将52改为13,看看这些数字的可管理性。如果你正在生成一个计算器,你仍然可以考虑刷新,这方面的数学计算要比把它拖到计算的中间简单得多。
如果没有别的:看看马丁·布罗德赫斯特的网站(它是同名的(,看看"组合算法"(它是C语言,非常可爱(,它将大大减少你的数字,使管理所有各种组合/排列等成为可能。你将使用几个不同的来获得你想要的数据。这也将使生活更容易,以确保你使用正确的算法。大多数都允许您指定映射到字符中,因此您可以用"T"代替10,以使对齐更容易,因为所有显示的都是单个字符。
即使您使用Martin的库,也可以在不简化流程的情况下生成一套完整的数据。
我不想因为家庭作业而责备你——我真的很好奇你为什么要生成这么多原始的Cribbage数据(这作为娱乐活动并不常见(
不久前,我遇到过很多论文(在500多门课程的水平上,或者在会议上的Cribbage演示中(,他们只用人工神经网络生成了策略性地与随机投掷相比掌握在手中的东西。他们只关注游戏的一小部分(有时,代码不对!(。对于这一级别的课程,我很惊讶他们竟然能远远超过赞助商。(如果他们知道就好了。(即使将人工神经网络应用于该剧也会更有趣、更复杂、更有趣。
最后一个想法——这是大多数人不会想到的——除了把分数掌握在手中之外的其他事情:
"你是发牌人,被发牌(随机(<1>、<2>、<3>、&lgt;4>、&llt;5>、<t;6>。你需要5分才能锁定,pone需要7分。由于pone将打出第一张牌,并将首先数牌,你对这六张牌的最佳投掷/保持策略是什么?"(然后提供分析,看看你是否能自己想出一两条规则(
怎么样:"如果你是经销商,并且在你的手牌上有19分,那么你的婴儿床上也有19分的几率是多少?"这些都是让游戏变得有趣的见解。