5

  • Question

    Even only 52 cards, the permutationIndex where I describe in Explanations section, would be a huge number; it is a number in one of 52!, and need 29 bytes to store.

    Thus I don't know a simple way to calculate the permutationIndex of a huge range, and store the index with a mininal cost, or maybe it can also be calculated. I'm thinking solution of this question would be three algorithms:

    1. An algorithm which compute the correct permutationIndex to implement the Dealing method

    2. An algorithm which compute the correct permutationIndex to implement the Collect method

    3. An algorithm which stores(or computes) permutationIndex with a minimal cost

  • Explanations

    I originally try to implement a integer handle generator of a range from int.MinVale to int.MaxValue using permutation.

    Because the range is really huge for that, thus I start from implement a Dealer class with 52 cards which doesn't really store a deck of cards like hashset or array, and even don't want random(except initial).

    With a given range of ordinal numbers, I consider every sequence of one of full permutations has a index, and named it permutationIndex. I use the index to remember which permutation it is and don't really store a sequence. The sequence is one of the possible order of the deck of card.

    And here is an example of emulation in animated graphics to show what I thought of. Enter image description here

    Everytime I dealt a card, I change the permutationIndex and dealt(count of dealt cards), that I know which cards are those dealt, and which are still in hand. When I collect a dealt card back, I'll know the card number, and put it on the top, it's also become the card for next time to deal. In the animation, colleted is the card number.

For more information, as follows.

  • Description of code

    A conceptual sample Dealer class for only three 3 is as following. The code is written in , and I'm also considering any solutions.

    Here're some descriptions of the sample code

    • With the method Dealing(), we get a number of the card which treat as dealt. It always returns the right most number (relevant to the array) and then rolls the number left from it (say the next available) to the right most position by changing permutationIndex.

    • The method Collect(int) is for collecting and put the dealt cards back into the deck. It would change permutationIndex also, according to what the number of card was returned back to the dealer.

    • The integer dealt tells how many cards we've dealt; from the left most to the count stored in dealt are dealt cards. With permutationIndex, we know the sequence of cards.

    • The int[,] array in the sample code is not used, just for helping imagine the permutations. The switch statements are considered to be implemented with algorithms which compute for the permutationIndex.

    • The permutationIndex is the same thing described in this answer of
      Fast permutation -> number -> permutation mapping algorithms

  • Sample code

    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;
}
Community
  • 1
  • 1
Ken Kin
  • 4,503
  • 3
  • 38
  • 76
  • 1
    Why not use auto-incremented value to get a new handle? – Sergey Vyacheslavovich Brunov Jan 31 '13 at 06:29
  • 1
    @KenKin, for example, you want the handle 1 will be available after `Release(1)`, i.e. next `GetHandle()` call will return handle 1? – Sergey Vyacheslavovich Brunov Jan 31 '13 at 06:37
  • 1
    Shouldn't this have a [tag:homework] tag? Edit: The tag is obsolete, however, should the question state it is a homework question? – Danny Varod Feb 03 '13 at 17:33
  • what do you wish to do? do you really mean "without storing the cards", or do you mean "without copying dealt cards and/or cards to be dealt, back and forwards between different variables in memory"? – Fredrik Feb 07 '13 at 19:14
  • 1
    Why not simply store an unordered list of the cards that have not be already dealt and randomly choose from it, removing the chosen card each time? This enables visualizing the uncertainty principle. If you want to simulate multiple decks opened in advance, start with a large list of undelt cards. If you want to simulate decks opened and shuffled in sequence, rebuild the list from a new deck each time the list empties out. If you want the process to be repetitive between simulations, use the same seed each time for the random function, otherwise, base seed on start time. – Danny Varod Feb 07 '13 at 19:51
  • 1
    Storing the `permuatationIndex` is just another way of storing the deck of cards ... – Henry Feb 08 '13 at 06:57
  • 4
    Storing the `permutationIndex` will need 29 bytes, Storing the deck in a byte array will need 52 bytes. That means you just gain 23 bytes but your code will be much longer and complex. So you trade a negligible reduction of data space for a significant increase of code space. – Henry Feb 08 '13 at 07:19
  • @Henry: Will the range of `int.MinValue` and `int.MaxValue` falls into the same situation? – Ken Kin Feb 08 '13 at 07:28
  • 1
    ***Why?!*** If gratuitous constraints turn you on, why not try writing a post that long without typing ascii 101. – Colonel Panic Feb 08 '13 at 16:05
  • Writing with that constraint is a [lipogram](http://en.wikipedia.org/wiki/Lipogram) – Colonel Panic Feb 08 '13 at 16:12
  • 1
    @Colonel Panic: Okay, I see. For the ***why***, because I don't know if it is necessarily more expensive than implemented in any other way. – Ken Kin Feb 08 '13 at 16:27
  • storing the deck will require 52 bits. You can have 52 bits, values are 0 or 1, which state which cards have been dealt. You can convert it into a number, but 2^52 is large so keep it binary – galchen Mar 01 '13 at 01:14
  • 1
    IMHO your approach is too much obsessed with *action* (dealing a card) I think: a card can be in (N+1) states: either it is on the deck, or in the hands of one of the players. There are some additional constraints (you consider the deck ordered, and the hands unordered, the total number of cards must be 52, each player has approximately the same number of cards, etc), but you should still be able to enumerate every *board state* (and find the transformations that correspond to the *actions* you need, and you are done. – wildplasser Mar 01 '13 at 01:32
  • 4
    "How can we accomplish this?" - accomplish *what*, precisely? There are more than 232 possible permutations, so unless you're happy with some sequences being impossible to deal, it's hard to see how you're going to manage with just an `int` as storage... – Jon Skeet Mar 01 '13 at 10:51
  • @JonSkeet: Thank you! I'm revising my question and trying to specify something clearly. – Ken Kin Mar 01 '13 at 15:22
  • Note that you only need 39 bytes to store the shuffled deck (6 bits per card). Are you really trying to save 10 bytes? Is that actually relevant? – Jon Skeet Mar 01 '13 at 17:00
  • 1
    @KenKin: I just think of the 6 bits as "we need to store 52 separate cards. 52 is more than 32 but less than or equal to 64, therefore we need 6 bits." I have no idea where hashes come into this, but then again it's still entirely unclear to me what you're trying to achieve. – Jon Skeet Mar 01 '13 at 17:43
  • 2
    I'm still not seeing a *question* - nor a reason to use a 29-byte integer with pretty complicated arithmetic instead of either a 52-byte or 39-byte array with the appropriate cards pre-dealt. – Jon Skeet Mar 01 '13 at 19:24
  • @JonSkeet: Ah.. the question is I don't know how to calculate the `permutionIndex`, and even don't know if there were algorithms which are not considered complicated. – Ken Kin Mar 01 '13 at 19:46
  • @KenKin can you explain more of the `Collect(int number)` ? Is the number an index, the number assigned to the card, or the number of cards? I can't figure out what you're trying to do with this. – Infinite Possibilities Mar 05 '13 at 21:52
  • 1
    @InfinitePossiblities: It's the card number. The card number collect back to the deck of card. It might be called elsewhere, so the returned number is not at any known order, it depends on the external caller. – Ken Kin Mar 05 '13 at 21:56

8 Answers8

1

If I've understood you right, the following code implements this:

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;
}
Ken Kin
  • 4,503
  • 3
  • 38
  • 76
Sergey Vyacheslavovich Brunov
  • 17,291
  • 7
  • 48
  • 81
1

Not exactly what you are trying to accomplish here, but if you want to deal from a random ordering of a deck of cards, you use a shuffle algorithm. The typical shuffle algorithm is Fisher-Yates. The shuffle algorithm will create an array listing the card numbers in random order ( 13,5,7,18,22,... etc ). To deal you start at the first element in the array and continue forward.

Tyler Durden
  • 11,156
  • 9
  • 64
  • 126
  • The amount of memory you would need to deal with permutations of 52! would be greater than the amount of memory needed for a shuffle. – Tyler Durden Feb 06 '13 at 18:55
  • I'm not saying to store full permutations, but a huge numerical index. We would need to store only one huge number. – Ken Kin Feb 06 '13 at 19:02
  • 3
    I know what is required. Any implementation that involves manipulating the permutation information for 52 different items will require a lot more memory than a shuffle. If you think you are saving memory or computational speed by avoiding a shuffle you are operating under a mistaken assumption. – Tyler Durden Feb 07 '13 at 15:38
  • 1
    Actually, storing 52 "ints" would take at least 52*(1 byte)=416 bits, or 52*(6 bits)=312 bits=39 bytes (considering we could store each card number in an integer number of bits, and pack them). This carries more information than just the permutation, which will carry 226 bits of information or 29 bytes. The computational overhead is huge, though, so it seems like the best way to go is to store 52 bytes. After all "minimal cost" isn't defined just by how much memory we use. Memory is much cheaper than CPU these days. Also, complexity is majorly reduced which makes it far easier to make it work. – DDS Feb 08 '13 at 17:22
  • Please note that when you paste all the bits of the list of cards together, you essentially get 1 huge number. The only real difference between this and a permutation number is that you can, in the list, store a deck that has duplicates. This takes up the extra bits. That base-52 list would take at least 297 bits vs 226 bits for the permutation. All in all, storing "1 huge number" is the exact same as storing a list of small numbers. – DDS Feb 08 '13 at 17:26
1

I am also struggling to see the whole picture here, but you could convert each permutation to base(52) with a single character representing each card and have a string representing each permutation.

So Spades could be 1-9 (ace - 9), 0ABC (10, J Q K), then DEFG... starting the hearts and so on.

So a deck of 3 cards, 2 Spade (2), 3 Heart (F) and 2 Diamond (say e), would have these permutation numbers:

2Fe
2eF
F2e
Fe2
eF2
e2F

You could convert these back and forth to a int/long/bigint by doing base 52 to base 10 conversions.

Here's an introduction to converting between bases.

So e2F would be F + 2*52 + e * 52^2 which would be 16 + 2*52 + 43*52*52 = 116392

So 116392 would be your permutation number.

(btw. I'm guessing about it 2 diamond being 'e' and 43, you can count it up and see exact what it would be)

Mike the Tike
  • 1,136
  • 8
  • 9
1

One way to tackle this is to use (pseudo)random number generator (like a Mersenne Twister), then store only the seed number for each deal. Since you get the same sequence of random numbers each time from the same seed, it serves to represent the whole deal (using the random numbers generated from that seed to drive what cards are dealt).

[edit...]

Some pseudo-code for the deal:

while (#cards < cardsNeed)
    card = getCard(random())
    if (alreadyHaveThisCard(card))
        continue
    [do something with the card...]
Mark Leighton Fisher
  • 5,609
  • 2
  • 18
  • 29
  • After you edit I understand what you told. I think that I don't really enumerate the cards unless that is necessary. Likely this question is used to replace `random` with *certain*. I originally describe this question in a `HandleGenerater`, but perhaps it confused people. A *dealer* class is, in fact, an analogy of such a generator. – Ken Kin Feb 08 '13 at 23:54
1

While I have a bit of a problem understanding what you are really trying to accomplish here, I suppose a coprime will generate a bunch of permutation numbers; that is: if you don't care too much about the distribution. You can use the Euclidian algorithm for that.

Algebra (set theory) states that you can simply use x = (x + coprime) % set.Length to get all elements in the set. I suppose each coprime is a permutation number as you describe it.

That said I'm not sure what distribution you get when using a generated coprime as 'random number generator'; I suppose certain distributions will occur more frequently than others and that a lot of distributions will be excluded from the generated numbers, for the simple reason that the generator will pick numbers in a ring. I'm being a bit creative here so perhaps it fits your needs, although it probably won't be the answer you're looking for.

atlaste
  • 30,418
  • 3
  • 57
  • 87
  • I'm actually not wanting random numbers. Instead, I want algorithms, which oprerates on the `permutationIndex`, whatever the number of a dealt card is collected, it only changes the index, so does `Dealing()`. Most of time we don't enumerate on the sequence of cards, and trying keep it *unknown* unless the enumeration is really needed. – Ken Kin Feb 10 '13 at 02:25
1

I really don't get your question, but I interpret it like this: you want to calculate the permutationIndex of a sequence of 52 cards. A given permutation index maps one-to-one to a sequence of cards. Since there are 52! possible arrangements of 52 cards, you'll need at least 226 bits, or 29 bytes. So, your permutationIndex will already be very big!

Since your permutation index is already 29 bytes long, some extra bytes won't make much of a difference and make the solution a lot easier.

For example, you could map each letter of the Latin alphabet to a card. Given that we have 26 lower case letters, 26 upper case letters, we have lo and behold 52 letters available to represent the 52 cards.

  abcdefghijklm      nopqrstuvwxyz
♥ A234567890JQK    ♦ A234567890JQK

  ABCDEFGHIJKLM      NOPQRSTUVWXYZ
♣ A234567890JQK    ♠ A234567890JQK

Now you can make a string of 52 letters. Each unique letter string represents a unique permutation of 52 cards. With this you can:

  • Generate a random string of letters to get a random permutation.
  • Immediately find out what card is where just by looking at the letter at a given position.
  • Shuffle, reorder, insert and remove cards easily.

Each character in a string is represented (in C#) as a 16-bit Unicode value, but for 52 cards you would only need 6 bits. So you have some more options to choose a representation:

  1. 832 bits, or 104 bytes: string of 52 Unicode characters
  2. 416 bits, or 52 bytes: array of 52 bytes
  3. 320 bits, or 40 bytes: array of 10 32-bit integers to hold 52 * 6 bits
  4. 312 bits, or 39 bytes: array of 39 bytes to hold 52 * 6 bits
  5. 226 bits, or 29 bytes: absolute lower bound

Representations 3 and 4 require quite some clever bit fiddling to get the 6 bits for a specific card out of the sequence. I would recommend representation 2, which preserves most of the advantages mentioned above.

When you are using a binary representation instead of a character string representation, then you can create an enum with a unique value for each card, and use that:

public enum Cards : byte
{
    HeartsAce
    HeartsTwo
    // ...
    HeartsTen
    HeartsJack
    HeartsQueen
    HeartsKing
    DiamondsAce
    DiamondsTwo
    // ...
    SpadesTen
    SpadesJack
    SpadesQueen
    SpadesKing
}
Daniel A.A. Pelsmaeker
  • 47,471
  • 20
  • 111
  • 157
  • @KenKin I don't really understand your comment. With 'I'm finding' you mean 'I need'? You need an algorithm to go from a permutation index to a sequence of cards and the other way around...? – Daniel A.A. Pelsmaeker Mar 06 '13 at 19:28
  • Thank you very much. I'm not a native English speaker. If the comment is confusing, then I'm removing it. What I mean is, I need to implement the class with the ways which do the things with the `permutationIndex`, and not other ways. – Ken Kin Mar 06 '13 at 19:43
1

You have working - and extremely efficient c# example for The kth Permutation of Order n (aka PermutationIndex) at this very old post:

For those interested in Combinations topic:

I suggest that you read through, before going into specific implementation.

Nenad
  • 24,809
  • 11
  • 75
  • 93
  • Thank you. How I operate on the index without enumerating it's elements? – Ken Kin Mar 07 '13 at 22:57
  • As I said, you have to read all article and check source code. Example would be: var result = new Permutation(3, 1).ToString(). You get this - "( 0 2 1 )", which is 2nd permutation (index 1), of 3 elements. – Nenad Mar 08 '13 at 19:05
  • I would think that I have a better implemention of that, though I implemented without it telling the index, but I think that I could; see [Check if permutations of characters are contained in text file](http://stackoverflow.com/questions/15218903/check-if-permutations-of-characters-are-contained-in-text-file/15234170#15234170). – Ken Kin Mar 08 '13 at 19:57
  • both these code based on the same algorithm; but my question is perform the operations with the index, according to some rule not known to me, without enumerating on the elements. This algorithm actually construct the index by internally built the sequence. Then I'd be better use a hashset or array directly, rather with `permutationIndex`. Thus, it's not the answer for me. – Ken Kin Mar 08 '13 at 19:58
  • Algorith doesn't enumarate on elements, but again, you would need to read article to know that. It is just capable to tell you "44th permutation of 5 elements is ....". And it is able to do few more things. Anyway... good luck! – Nenad Mar 08 '13 at 20:43
0

Like the others I am not sure what you want to do but if you want to save as much space a possible on the communication/storage of the dealt cards I would do the following:

I would store the cards dealt on a single Long using a enum with the flag attribute so I could use bitwise comparisons to see which card has been dealt.

Because each card is a separate "flag" with a unique number which is set to the exponent of 2 so they will never clash.

In total even if you deal all the cards the storage will still be 8 bytes. any extra data you need you can bolt on the end.

Please see the working example below.

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,

        }
    }
}
dmportella
  • 4,614
  • 1
  • 27
  • 44