问题
即使只有 52 张卡片,
permutationIndex
我在解释部分中描述的地方,也将是一个巨大的数字;它是其中之一的数字52!
,需要 29 个字节来存储。因此我不知道一个简单的方法来计算
permutationIndex
一个巨大的范围,并以最小的成本存储索引,或者它也可以计算出来。我在想这个问题的解决方案是三种算法:一种计算正确
permutationIndex
实现方法的算法Dealing
一种计算正确
permutationIndex
实现方法的算法Collect
一种以最小成本存储(或计算)的算法
permutationIndex
解释
我最初尝试实现一个范围从使用排列到使用排列的整数句柄生成器。
int.MinVale
int.MaxValue
因为这个范围真的很大,所以我从实现一个
Dealer
有 52 张卡片的类开始,它并没有真正存储像 hashset 或数组这样的卡片组,甚至不想要随机的(除了初始)。对于给定的序数范围,我认为全排列之一的每个序列都有一个索引,并将其命名为
permutationIndex
。我使用索引来记住它是哪种排列,而不是真正存储序列。顺序是一副牌的可能顺序之一。这是动画图形中的仿真示例,以显示我的想法。
每次我发牌时,我都会更改
permutationIndex
和dealt
(发牌数),这样我就知道哪些牌是已发牌的,哪些牌仍在手中。当我把一张发牌收回来时,我会知道卡号,并把它放在上面,它也成为下次发牌的牌。在动画中,colleted
是卡号。
欲了解更多信息,如下所示。
代码说明
仅三个 3的概念样本
Dealer
类如下。代码是用c#编写的,我也在考虑任何与语言无关的解决方案。以下是示例代码的一些说明
使用该方法
Dealing()
,我们得到了作为已发牌的牌号。它总是返回最右边的数字(与数组相关),然后通过改变permutationIndex
.该方法
Collect(int)
用于收集并放回发牌的牌组。它也会permutationIndex
根据返回给经销商的牌号而改变。整数
dealt
表示我们发了多少张牌;从最左边到存储的计数dealt
是发牌。有了permutationIndex
,我们就知道了卡片的顺序。示例代码中的
int[,]
数组未使用,仅用于帮助想象排列。switch语句被认为是用计算permutationIndex
.这与快速排列->数字->排列映射算法
permutationIndex
的答案中描述的相同
示例代码
public static class Dealer { public static void Collect(int number) { if(1>dealt) throw new IndexOutOfRangeException(); switch(permutationIndex) { case 5: case 0: switch(number) { case 3: break; case 2: permutationIndex=1; break; case 1: permutationIndex=4; break; } break; case 4: case 3: switch(number) { case 3: permutationIndex=5; break; case 2: permutationIndex=2; break; case 1: break; } break; case 2: case 1: switch(number) { case 3: permutationIndex=0; break; case 2: break; case 1: permutationIndex=3; break; } break; } --dealt; } public static int Dealing() { if(dealt>2) throw new IndexOutOfRangeException(); var number=0; switch(permutationIndex) { case 5: permutationIndex=3; number=3; break; case 4: permutationIndex=0; number=1; break; case 3: permutationIndex=1; number=1; break; case 2: permutationIndex=4; number=2; break; case 1: permutationIndex=5; number=2; break; case 0: permutationIndex=2; number=3; break; } ++dealt; return number; } static int[,] sample= new[,] { { 1, 2, 3 }, // 0 { 1, 3, 2 }, // 1 { 3, 1, 2 }, // 2 { 3, 2, 1 }, // 3 { 2, 3, 1 }, // 4 { 2, 1, 3 }, // 5 }; static int permutationIndex; static int dealt; }