6
  • 问题

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

    因此我不知道一个简单的方法来计算permutationIndex一个巨大的范围,并以最小的成本存储索引,或者它也可以计算出来。我在想这个问题的解决方案是三种算法:

    1. 一种计算正确permutationIndex实现方法的算法Dealing

    2. 一种计算正确permutationIndex实现方法的算法Collect

    3. 一种以最小成本存储(或计算)的算法permutationIndex

  • 解释

    我最初尝试实现一个范围从使用排列到使用排列的整数句柄生成器int.MinValeint.MaxValue

    因为这个范围真的很大,所以我从实现一个Dealer有 52 张卡片的类开始,它并没有真正存储像 hashset 或数组这样的卡片组,甚至不想要随机的(除了初始)。

    对于给定的序数范围,我认为全排列之一的每个序列都有一个索引,并将其命名为permutationIndex。我使用索引来记住它是哪种排列,而不是真正存储序列。顺序是一副牌的可能顺序之一。

    这是动画图形中的仿真示例,以显示我的想法。 在此处输入图像描述

    每次我发牌时,我都会更改permutationIndexdealt(发牌数),这样我就知道哪些牌是已发牌的,哪些牌仍在手中。当我把一张发牌收回来时,我会知道卡号,并把它放在上面,它也成为下次发牌的牌。在动画中,colleted卡号


欲了解更多信息,如下所示。

  • 代码说明

    仅三个 3的概念样本Dealer类如下。代码是用编写的,我也在考虑任何与解决方案。

    以下是示例代码的一些说明

    • 使用该方法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;
    }
    
4

8 回答 8

1

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

于 2013-02-06T18:36:04.910 回答
1

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

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

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

于 2013-02-09T15:53:43.350 回答
1

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

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;
}
于 2013-01-31T06:50:58.153 回答
1

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

[编辑...]

交易的一些伪代码:

while (#cards < cardsNeed)
    card = getCard(random())
    if (alreadyHaveThisCard(card))
        continue
    [do something with the card...]
于 2013-02-08T19:33:57.817 回答
1

我真的不明白你的问题,但我这样解释:你想计算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 位。因此,您有更多选择来选择表示:

  1. 832 位或 104 字节:由 52 个 Unicode 字符组成的字符串
  2. 416 位或 52 字节:52 字节数组
  3. 320 位或 40 字节:包含 10 个 32 位整数的数组,可容纳 52 * 6 位
  4. 312 位,或 39 字节:39 字节数组,可容纳 52 * 6 位
  5. 226 位或 29 字节:绝对下限

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


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

public enum Cards : byte
{
    HeartsAce
    HeartsTwo
    // ...
    HeartsTen
    HeartsJack
    HeartsQueen
    HeartsKing
    DiamondsAce
    DiamondsTwo
    // ...
    SpadesTen
    SpadesJack
    SpadesQueen
    SpadesKing
}
于 2013-03-06T19:14:19.593 回答
1

我也很难在这里看到全貌,但是您可以将每个排列转换为 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^216 + 2*52 + 43*52*52 = 116392

所以 116392 将是你的排列数。

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

于 2013-02-07T19:56:27.443 回答
1

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

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


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

于 2013-03-07T22:34:14.410 回答
0

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

我会使用带有标志属性的枚举将发牌存储在单个 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,

        }
    }
}
于 2013-03-07T11:51:07.927 回答