6

  • 質問

    説明permutationIndexセクションで説明した 52 枚のカードだけでも膨大な数になります。のいずれかの数値であり、格納するには 29 バイトが必要です。52!

    したがって、巨大な範囲のを計算し、最小限のコストでインデックスを保存する簡単な方法がわかりません。または、計算することもできます。permutationIndexこの質問の解決策は、次の 3 つのアルゴリズムになると考えています。

    1. メソッドpermutationIndexを実装Dealingするための正しい計算アルゴリズム

    2. メソッドpermutationIndexを実装Collectするための正しい計算アルゴリズム

    3. 最小限のコストで格納 (または計算) するアルゴリズムpermutationIndex

  • 説明

    私は元々、順列を使用してから までの範囲の整数ハンドル ジェネレーターを実装しようとしています。int.MinValeint.MaxValue

    その範囲は非常に大きいため、ハッシュセットや配列などのカードのデッキを実際に格納せず、ランダム(初期を除く) を必要としない 52 枚のカードを持つクラスを実装することから始めます。Dealer

    与えられた範囲の序数を使用して、完全順列のいずれかのすべてのシーケンスにインデックスがあると見なし、名前を付けましたpermutationIndex。私はインデックスを使用してそれがどの順列であるかを覚えており、実際にはシーケンスを保存していません。シーケンスは、カードのデッキの可能な順序の 1 つです。

    そして、私が考えたことを示すために、アニメーション グラフィックスでのエミュレーションの例を示します。 ここに画像の説明を入力してください

    permutationIndexカードを配るたびにand (配られたカードの数) を変更し、dealtどのカードが配られ、どのカードがまだ手元にあるかを知っています。配られたカードの裏を集めるとカード番号がわかるので、一番上に置くと次回配るカードにもなります。アニメーションでcolletedは、 はカード番号です。

詳細については、次のとおりです。

  • コードの説明

    Dealer3 つのみの概念的なサンプルクラスは次のとおりです。コードはソリューションも検討しています。

    サンプルコードの説明を次に示します。

    • メソッドで、配られたカードの枚数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

ここで達成しようとしているものとは正確には異なりますが、カードのデッキのランダムな順序から対処したい場合は、シャッフル アルゴリズムを使用します。典型的なシャッフル アルゴリズムはFisher-Yatesです。シャッフル アルゴリズムは、ランダムな順序 (13、5、7、18、22、... など) でカード番号をリストする配列を作成します。対処するには、配列の最初の要素から始めて、先に進みます。

于 2013-02-06T18:36:04.910 に答える
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

ここであなたが実際に何を達成しようとしているのかを理解するのに少し問題がありますが、余素は一連の順列数を生成すると思います。つまり、ディストリビューションをあまり気にしない場合です。そのためにユークリッド アルゴリズムを使用できます。

代数 (集合論) では、単に x = (x + coprime) % set.Length を使用して集合内のすべての要素を取得できると述べています。あなたが説明したように、各余素は順列数であると思います。

そうは言っても、生成された余素を「乱数ジェネレーター」として使用すると、どのような分布が得られるかわかりません。特定の分布が他の分布よりも頻繁に発生し、多くの分布が生成された数値から除外されると思います。これは、ジェネレーターがリング内の数値を選択するという単純な理由からです。私はここで少し創造的であるため、おそらくあなたのニーズに合っているかもしれませんが、おそらくあなたが探している答えではないでしょう.

于 2013-02-09T15:53:43.350 に答える
1

あなたの質問はよくわかりませんが、私は次のように解釈します: permutationIndex52 枚のカードのシーケンスの 指定された順列インデックスは、一連のカードに 1 対 1 でマップされます。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 バイト: 52 * 6 ビットを保持する 10 個の 32 ビット整数の配列
  4. 312 ビット、または 39 バイト: 52 * 6 ビットを保持する 39 バイトの配列
  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... ハートの開始などです。

したがって、スペード (2) 2 つ、ハート (F) 3 つ、ダイヤ (e) 2 枚の 3 枚のカードのデッキには、次の順列番号があります。

2Fe
2eF
F2e
Fe2
eF2
e2F

base 52 から base 10 への変換を行うことで、これらを int/long/bigint に前後に変換できます。

基数変換の紹介です。

したがって、e2FはF + 2*52 + e * 52^2どちらになりますか16 + 2*52 + 43*52*52 = 116392

したがって、116392 が順列番号になります。

(ところで、2 つのひし形が「e」であり、43 であると推測しています。数えてみると、それが何であるかを正確に確認できます)

于 2013-02-07T19:56:27.443 に答える
1

これに取り組む 1 つの方法は、(疑似) 乱数ジェネレーター ( Mersenne Twisterなど) を使用し、各取引のシード番号のみを保存することです。同じシードから毎回同じ一連の乱数を取得するため、ディール全体を表すのに役立ちます (そのシードから生成された乱数を使用して、配られるカードを操作します)。

[編集...]

取引の擬似コード:

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

他の人たちと同じように、あなたが何をしたいのかわかりませんが、配られたカードの通信/保管にできるだけ多くのスペースを節約したい場合は、次のようにします。

flag 属性を持つ列挙型を使用して、配られたカードを 1 つの 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 に答える