c# - 如何在不存储一副牌的情况下实现经销商类？

Question

问题

即使只有 52 张卡片，permutationIndex我在解释部分中描述的地方，也将是一个巨大的数字；它是其中之一的数字52!，需要 29 个字节来存储。

因此我不知道一个简单的方法来计算permutationIndex一个巨大的范围，并以最小的成本存储索引，或者它也可以计算出来。我在想这个问题的解决方案是三种算法：
1. 一种计算正确permutationIndex实现方法的算法Dealing
2. 一种计算正确permutationIndex实现方法的算法Collect
3. 一种以最小成本存储（或计算）的算法permutationIndex
解释

我最初尝试实现一个范围从使用排列到使用排列的整数句柄生成器。int.MinValeint.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;
}

score 1 · Accepted Answer

不完全是你在这里想要完成的，但如果你想从一副牌的随机顺序中进行交易，你可以使用洗牌算法。典型的 shuffle 算法是Fisher-Yates。洗牌算法将创建一个以随机顺序（13、5、7、18、22、...等）列出卡号的数组。要处理，您从数组中的第一个元素开始并继续前进。

score 1 · Accepted Answer

虽然我在理解你在这里真正想要完成的事情时遇到了一点问题，但我想一个互质数会生成一堆排列数；那就是：如果你不太关心分布。您可以为此使用欧几里得算法。

代数（集合论）指出，您可以简单地使用 x = (x + coprime) % set.Length 来获取集合中的所有元素。我想每个互质数都是您描述的排列数。

也就是说，当使用生成的互质数作为“随机数生成器”时，我不确定你会得到什么分布；我想某些分布会比其他分布更频繁地发生，并且很多分布将从生成的数字中排除，原因很简单，生成器会在一个环中选择数字。我在这里有点创意，所以也许它符合您的需求，尽管它可能不是您正在寻找的答案。

score 1 · Accepted Answer

如果我的理解正确，下面的代码实现了这一点：

public class Dealer {
    public int Dealing() {
        var number=
            _freeCards.Count>0
                ?_freeCards.Dequeue()
                :_lastNumber++;

        _dealtCards.Add(number);
        return number;
    }

    public void Collect(int number) {
        if(!_dealtCards.Remove(number))
            throw new ArgumentException("Card is not in use", "number");

        _freeCards.Enqueue(number);
    }

    readonly HashSet<int> _dealtCards=new HashSet<int>();
    readonly Queue<int> _freeCards=new Queue<int>(); // "Pool" of free cards.
    int _lastNumber;
}

score 1 · Accepted Answer

解决此问题的一种方法是使用（伪）随机数生成器（如Mersenne Twister），然后仅存储每笔交易的种子数。由于您每次都从同一个种子中获得相同的随机数序列，因此它可以代表整个发牌（使用从该种子生成的随机数来驱动发牌）。

[编辑...]

交易的一些伪代码：

while (#cards < cardsNeed)
    card = getCard(random())
    if (alreadyHaveThisCard(card))
        continue
    [do something with the card...]

score 1 · Accepted Answer

我真的不明白你的问题，但我这样解释：你想计算permutationIndex52 张牌的序列。给定的排列索引一对一地映射到一系列卡片。因为有52个！52 卡的可能排列，您至少需要 226 位或 29 字节。所以，你的permutationIndex会已经很大了！

由于您的排列索引已经有 29 个字节长，因此一些额外的字节不会产生太大影响，并使解决方案更容易。

例如，您可以将拉丁字母的每个字母映射到一张卡片。鉴于我们有 26 个小写字母和 26 个大写字母，我们有52个字母可用于表示 52 张卡片。

  abcdefghijklm nopqrstuvwxyz
♥ A234567890JQK ♦ A234567890JQK

  ABCDEFGHIJKLM NOPQRSTUVWXYZ
♣ A234567890JQK ♠ A234567890JQK

现在你可以制作一个由 52 个字母组成的字符串。每个唯一的字母串代表 52 张卡片的唯一排列。有了这个，你可以：

生成随机的字母串以获得随机排列。
只需查看给定位置的字母，即可立即找出卡片在哪里。
轻松洗牌、重新排序、插入和取出卡片。

字符串中的每个字符（在 C# 中）表示为 16 位 Unicode 值，但对于 52 位卡，您只需要 6 位。因此，您有更多选择来选择表示：

832 位或 104 字节：由 52 个 Unicode 字符组成的字符串
416 位或 52 字节：52 字节数组
320 位或 40 字节：包含 10 个 32 位整数的数组，可容纳 52 * 6 位
312 位，或 39 字节：39 字节数组，可容纳 52 * 6 位
226 位或 29 字节：绝对下限

表示 3 和 4 需要相当巧妙的位摆弄才能使特定卡的 6 位脱离序列。我会推荐表示 2，它保留了上面提到的大部分优点。

当您使用二进制表示而不是字符串表示时，您可以为每张卡创建一个具有唯一值的枚举，并使用它：

public enum Cards : byte
{
    HeartsAce
    HeartsTwo
    // ...
    HeartsTen
    HeartsJack
    HeartsQueen
    HeartsKing
    DiamondsAce
    DiamondsTwo
    // ...
    SpadesTen
    SpadesJack
    SpadesQueen
    SpadesKing
}

score 1 · Accepted Answer

我也很难在这里看到全貌，但是您可以将每个排列转换为 base(52)，用一个字符表示每张卡片，并用一个字符串表示每个排列。

所以黑桃可能是1-9 (ace - 9), 0ABC (10, J Q K), 然后DEFG... 开始红心等等。

因此，一副 3 张牌，2 黑桃 (2)、3 心 (F) 和 2 钻石（比如 e），将具有以下排列数：

2Fe
2eF
F2e
Fe2
eF2
e2F

您可以通过将基数 52 转换为基数 10 来将这些来回转换为 int/long/bigint。

下面介绍bases之间的转换。

所以 e2F 将F + 2*52 + e * 52^2是16 + 2*52 + 43*52*52 = 116392

所以 116392 将是你的排列数。

（顺便说一句。我猜它 2 钻石是 'e' 和 43，你可以数一数，看看它会是什么）

score 1 · Accepted Answer

在这个非常古老的帖子中，您有工作 - 并且非常有效的 c# 示例，用于Order n 的第 k 个排列（又名 PermutationIndex）：

http://msdn.microsoft.com/en-us/library/Aa302371.aspx#permutat_topic3

对于那些对组合主题感兴趣的人：

我建议您在进入具体实施之前通读一遍。

score 0 · Accepted Answer

像其他人一样，我不确定你想做什么，但如果你想尽可能多地节省已处理卡片的通信/存储空间，我会执行以下操作：

我会使用带有标志属性的枚举将发牌存储在单个 Long 上，这样我就可以使用按位比较来查看发了哪张牌。

因为每张卡片都是一个单独的“标志”，其唯一编号设置为 2 的指数，因此它们永远不会发生冲突。

总的来说，即使你处理了所有的牌，存储空间仍然是 8 个字节。您需要的任何额外数据都可以在最后进行。

请参阅下面的工作示例。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication12
{
    class Program
    {
        static void Main(string[] args)
        {
            // Because each card is unique you could use Flag attributed Enum see the enum below and set each item a unique value I used 2 to the power of 52
            Cards cardsdealt = Cards.Clubs_10 | Cards.Clubs_2 | Cards.Diamonds_3;

            if ((cardsdealt & Cards.Clubs_10) == Cards.Clubs_10)
            {
                Console.WriteLine("Card.Clubs_10 was dealt");
            }

            // Storage would always be 8 bytes for the long data type
        }

        [Flags]
        public enum Cards : long
        {
            Spades_Ace = 1,
            Spades_2 = 2,
            Spades_3 = 4,
            Spades_4 = 8,
            Spades_5 = 16,
            Spades_6 = 32,
            Spades_7 = 64,
            Spades_8 = 128,
            Spades_9 = 256,
            Spades_10 = 512,
            Spades_Jack = 1024,
            Spades_Queen = 2048,
            Spades_King = 4096,
            Hearts_Ace = 8192,
            Hearts_2 = 16384,
            Hearts_3 = 32768,
            Hearts_4 = 65536,
            Hearts_5 = 131072,
            Hearts_6 = 262144,
            Hearts_7 = 524288,
            Hearts_8 = 1048576,
            Hearts_9 = 2097152,
            Hearts_10 = 4194304,
            Hearts_Jack = 8388608,
            Hearts_Queen = 16777216,
            Hearts_King = 33554432,
            Diamonds_Ace = 67108864,
            Diamonds_2 = 134217728,
            Diamonds_3 = 268435456,
            Diamonds_4 = 536870912,
            Diamonds_5 = 1073741824,
            Diamonds_6 = 2147483648,
            Diamonds_7 = 4294967296,
            Diamonds_8 = 8589934592,
            Diamonds_9 = 17179869184,
            Diamonds_10 = 34359738368,
            Diamonds_Jack = 68719476736,
            Diamonds_Queen = 137438953472,
            Diamonds_King = 274877906944,
            Clubs_Ace = 549755813888,
            Clubs_2 = 1099511627776,
            Clubs_3 = 2199023255552,
            Clubs_4 = 4398046511104,
            Clubs_5 = 8796093022208,
            Clubs_6 = 17592186044416,
            Clubs_7 = 35184372088832,
            Clubs_8 = 70368744177664,
            Clubs_9 = 140737488355328,
            Clubs_10 = 281474976710656,
            Clubs_Jack = 562949953421312,
            Clubs_Queen = 1125899906842620,
            Clubs_King = 2251799813685250,

        }
    }
}

c# - 如何在不存储一副牌的情况下实现经销商类？

8 回答 8

Related

Reference