How to calculate specific cards combination index

Question

There are 22100 combinations of 3 cards from the 52 cards deck (52 * 51 * 50 / 3! = 22100).

Here is an enumeration of all these combinations:

    static const ins cards_count = 52;
    int boardId = 0;

    for (int b1 = 0; b1 < card_count; b1++)
    { 
        for (int b2 = b1 + 1; b2 < card_count; b2++)
        {
            for (int b3 = b2 + 1; b3 < card_count; b3++)
            {
               cout << boardId << endl;
               boardId++;
            }
        }
    }

Is it posssible to write an indexer fucntion that converts b1, b2, b3 to the boardId (without using a map)? If this is hard maybe you can advise some hash fucntion that maps b1, b2, b3 to the int size hash.

This is a maths problem not a programming problem, and yes I'm sure its possible. — john, Feb 27 '18 at 11:19
is it possible? Your code already does that. Well, almost... you just need to add a `if(b1==b1_target && b2==b2_target && b3==b3_target) return boardId`. not the most efficient, but enough to see that it is possible — 463035818_is_not_an_ai, Feb 27 '18 at 11:19
@Brans Ds Do you just want to assign and get a unique id for each set of combination (of 3 cards)? If that is the case, there is no need to calculate the number of combinations at all. — user3437460, Feb 27 '18 at 11:42
@user3437460 This not so beautiful, but it will ok to for the my task — Brans Ds, Feb 27 '18 at 11:43
Related/dupe for Python: [Compute rank of a combination?](https://stackoverflow.com/questions/3143142/compute-rank-of-a-combination/3143594) and also related for C++ [Fast ranking/unranking of combinations (64bit)](https://stackoverflow.com/questions/38590286/fast-ranking-unranking-of-combinations-64bit) — jdehesa, Feb 27 '18 at 11:45

score 3 · Accepted Answer · answered Feb 27 '18 at 11:29

There is. It's pretty straightforward, too, and I briefly thought about writing down how, but then I realized I need quite a lot of mathematical notation for it.

The idea is to calculate how many combinations come before (or after) the one you need an index for.

The 3 from 52 combinations you state are correct, of course. Now let's enumerate how many come before b1,b2,b3:

First of all, there are all combinations with the first card smaller than b1. You have b1 options for the first card (since you start at 0), and for each of these options b1_, you have 52-b1_ choose 2 combinations. So, this number is the sum over b1_ from 0 to b1-1 over said binomial coefficient. With a little of math knowledge, you can derive a closed formula for that without actually evaluting a sum.
Second, there is all combinations with the first card having index b1 and the second card having index below b2. This is again a sum, but an easier one. You have one choice for the first card (b1) and b2-b1 (might be off by one, check that before you implement it) options for the second card. For each of these options (sum over b2_) you have 52-b2 options for the third card. This is a sum over consecutive numbers, and getting a closed formula for that is simple (hint: the sum of the first n numbers, starting at 1, is n*(n+1)/2, the sum of consecutive numbers not starting at one is the difference between two sums starting at 1).
Finally, you are interested in the number of combinations with the first two cards being b1 and b2 and the third being smaller than b3. This is simple, since that sum is exactly b3.

Only thing you need to do now is add the result from each item, and you have your index. I advise you take a piece of paper, do the math as proposed and get to a simple, easy to evaluate formula you can implement.

score 0 · Answer 2 · answered Feb 27 '18 at 13:04

I would simply ignore the fact that cards in a set must be unique and sorted. Then your index is simply card1 + 52 * card2 + 52 * 52 * card3. With well formed sets not every index is reachable and the distribution is skewed towards lower numbers. Try hash = index % prime * 52 * 52 * 52 + index to even out the distribution. Try a low prime. The index part added ensures the hash will remain unique.

user3437460 · Answer 3 · 2018-02-27T11:56:47.223

-1

If you are only interested to assign and get the unique id of a set of any 3 different cards from a standard deck, there is no need to calculate the number of combinations for various set.

Let the cards in the deck be assigned with 1 to 52.

You could do it programatically as :

int getSetId (int card1, int card2, int card3){
    if (card1 == card2 || card2 == card3 || card1 == card3)
        //throw an exception
    return (card1 * card2 * card3);
}

This will give you an unique id for all set combinations.

Edit 1:

In case there will be a duplicated id due to the multipliers forming the same product, instead of using 1 to 52, you can use the first 52 prime numbers.

edited Feb 27 '18 at 11:56

answered Feb 27 '18 at 11:51

user3437460

17,253
15
58
106

It returns unique value but it is bad as a hash function. It is producing values only in the beginning, if we divide it output to 6 parts here is distribution: 0.737783 0.164706 0.0648416 0.0246606 0.00723982 0.000769231 – Brans Ds Feb 27 '18 at 12:12
What are you dividing it by? I thought you just wanted the unique id? No? – user3437460 Feb 27 '18 at 12:15
To use it like hash function.. and hash function should produce balanced output to be effective – Brans Ds Feb 27 '18 at 12:19
1

I dont understand how this results in unique ids. For example `getSetId(3,2,4)` yields the same id as `getSetId(3,1,8)`, one has to use prime numbers to make it work – 463035818_is_not_an_ai Feb 27 '18 at 12:26
@user463035818 Yes, it will be prime numbers (as already mentioned in my post) – user3437460 Feb 27 '18 at 12:50
@Brans Ds If you want to generare hash values, you can apply quadratic probing. – user3437460 Feb 27 '18 at 12:53
1

your answer states: "Let the cards in the deck be assigned with 1 to 52." and then "This will give you an unique id for all set combinations.". The remark about prime numbers looks like a sideremark, but actually "In case there will be a duplicated id" is just the case when you use anything else than primes – 463035818_is_not_an_ai Feb 27 '18 at 12:54

How to calculate specific cards combination index

3 Answers3