The hand and deal definitions may seem obvious, but the word "hand" is often used for both meanings, as in the conversation: "Did you bid the slam on hand six?" "No, I miscounted my hand." To add clarity, I use these definition.
This page will assume some basic combinatorics.
There are exactly
D=53644737765488792839237440000different bridge deals. This number is:
52!
-------
4
(13!)
Is there a way to encode deals to numbers from 0 to D-1?
The answer is, "yes."
S : 8
H : AKQT4
D : AJ6
C : T742
S : A6543 S : 9
H : 987 H : J53
D : 753 D : KQ92
C : A3 C : QJ985
S: KQJT72
H: 62
D: T84
C: K6
We initially encode this as:
-->WSSSSENSWWWWSNNNENWWWSENESNEENSESWNWSWEWSEENEENSENWN
The first "W" means that west got the ace of spades. Since south
got the king, queen, jack, and ten of spades, the next four letters
are "S"s. The next letter, "E", indicates that east got the nine of
spades, etc.
Now, we write down the locations of all the north cards in this deal (with the "Ace of spade" being card 0):
--> N NNN N N N N N N N N N
6 13-15 17 23 26 29 34 43 46 49 51
Yielding the sequence:
Nseq = [ 6 13 14 15 17 23 26 29 34 43 46 49 51 ]In general, Nseq can be any 13-element subset of the set of numbers from 0 to 51.
Now, remove the N's from the original sequence and remove the gaps, yielding the 39 character string:
-->WSSSSESWWWWSEWWWSEESEESESWWSWEWSEEEESEW
We do the same for east with this new string as we did for north
above:
--> E E EE EE E E EEEE E
To get the sequence:
Eseq = [ 5 12 17 18 20 21 23 29 32 33 34 35 37 ]
This is a sequence of 13 numbers between 0 and 38.
Lastly, we delete the E's from the list to get:
-->WSSSSSWWWWSWWWSSSSWWSWWSSW
We apply the same procedure to south with this 26-character string,
and we get:
Sseq = [ 1 2 3 4 5 10 14 15 16 17 20 23 24 ]
This always yields a set of 13 numbers from 0 to 25.
We could define Wseq, but it is always the same - once you've given north, east, and south their cards, west gets whatever is left.
Notice, only Nseq tells us precisely which card is held by the hand. For example, the Nseq has the number "29", which indicates that card 29 (the jack of diamonds) is in the north hand. But "29" is also in the Eseq list. That's because the east hand has the 29th card in the deck *after* we've removed the cards which go to north.
What if someone gives you three collections, Nseq, Eseq, and Sseq, with Nseq bounded above by 51, Eseq bounded by 38, and Sseq bounded by 25? Can we create a deal from that?
Yes. Let do an example:
Nseq=[ 5 15 21 22 26 33 34 36 42 47 49 50 51 ] Eseq=[ 0 1 3 7 8 10 11 17 20 29 32 35 36 ] Sseq=[ 1 3 4 6 9 11 12 17 18 20 21 24 25 ]We start with a mystery deal:
-->????????????????????????????????????????????????????
But we know that Nseq tells us precisely which cards go to north.
So we mark those cards:
-->?????N?????????N?????NN???N??????NN?N?????N????N?NNN
But the Eseq now tells us precisely which of the remaining mystery
cards goes to east. So we can place the east cards:
-->EE?E?N??EE?EE??N???E?NN?E?N??????NN?NE??E?N?EE?N?NNN
Now that we've placed the east cards, the Sseq tells us precisely
which of the remaining cards go to south.
-->EE?ESN?SEESEE?SN??SE?NNSESN????SSNN?NESSE?N?EESNSNNN
But the rest of the mystery cards have to go to west, giving us the
deal:
-->EEWESNWSEESEEWSNWWSEWNNSESNWWWWSSNNWNESSEWNWEESNSNNN
which, written out long, is:
S : 9
H : Q65
D : A764
C : J6432
S : Q8 S : AKJ6532
H : AJT7 H : 83
D : KQJT5 D : 3
C : QT C : K98
S: T74
H: K942
D: 982
C: A75
So the triplets (Nseq,Eseq,Sseq) determines the deal completely, and no
two triplets lead to the same deal.
Now there are Choose(52,13) different Nseq's, because Nseq's arise by picking 13 numbers from a set of 52 numbers. Similarly, there are Choose(39,13) Eseq's, and Choose(26,13) Eseq's. This yields another formula for the number of deals:
D = Choose(52,13) * Choose(39,13) * Choose(26,13)
Let's say we are looking at 3-subsets of the 6-set {0,1,2,3,4,5}. We can list them in the following order:
012
013
023
123
014
024
124
034
134
234
015
025
125
035
135
235
045
145
245
345
How does this order work? To compare two subsets, we always look at the largest elements first. So "125" is later in the order than "234", because the largest element of "125" is larger than the largest element of "234." If their largest elements are the same, we compare the second largest elements. So "145" is later in the order than "235". We keep going backwards through the subsets, until we find a point where they differ.
The beauty of this order is that we can find a subset's index in the order fairly quickly. We'll use "235" as an example.
We know that all of the 3-subsets of {0,1,2,3,4} come before it. There are Choose(5,3)=10 of those.
We also know that all the 3-subsets with 5 of the form "xy5", where x and y are in {0,1,2}, come before it. There are Choose(3,2)=3 of those.
Last, we know that all the subsets of the form "x35" , with x in {0,1} come before "235". There are Choose(2,1)=2 ways of picking that x.
So there are
Choose(5,3)+Choose(3,2)+Choose(2,1)=10+3+2=15different sets before "235". If we index these sets starting at 012 with index zero, "235" would have index 15.
Let's look at that formula for the index of 235. Notice, that the operands of the choose operator are (5,3), (3,2), (2,1), and that the left operands are 5, 3, and 2, precisely the elements of our set! The right operands are (3,2,1). If we think about our argument to find 235's index in the order, we can see that this pattern is always true. If we have an n-set {x1 < x2 < x3 < ... < xn}, its index in the squashed order on n-sets is:
(*) Choose(xn,n)+Choose(x(n-1),n-1)+...+Choose(x1,1)
Also, notice that the squashed order index of a subset is independent of the set from which we are taking it. "235" has index 15 in the squashed order whether we consider it as a 3-subset of {0,1,2,3,4,5} or as a 3-subset of {0,1,...,100}. That's because all of the 3-subsets with elements greater than 5 come after 235 in the order, so they don't affect the index of 235.
Now, our Nseq, Eseq, and Sseq are just 13-sets, and we can determine their indices easily using (*).
For example, for our original Nseq:
Nseq = [ 6 13 14 15 17 23 26 29 34 43 46 49 51 ]
The index should be:
Index(Nseq)=
Choose(51,13) + Choose(49,12) + Choose(46,11) + Choose(43,10) +
Choose(34,9) + Choose(29,8) + Choose(26,7) + Choose(23,6) +
Choose(17,5) + Choose(15,4) + Choose(14,3) + Choose(13,2) +
Choose(6,1)
The index for the Nseq will be a unique number between 0 and Choose(52,13)-1, the index for the Eseq will be a unique number between 0 and Choose(39,13)-1, and the index for the Sseq will be a unique number between 0 and Choose(26,13)-1.
So now we have a correspondence between triplets of 13-sets:
(Nseq,Eseq,Sseq)
and triples of numbers:
(Nindex,Eindex,Sindex)
with
0 <= Nindex < Choose(52,13)= NMax
0 <= Eindex < Choose(39,13) = EMax
0 <= Sindex < Choose(26,13) = SMax
We can now use this second triple to come up with the index for the entire deal:
DealIndex = Nindex*Emax*Smax + Eindex*Smax + Sindex
This index will be a unique number between 0 and NMax*Emax*Smax-1, which is precisely what we wanted.
From an arbitrary index "I" in this range, we get get a triple of numbers back by first dividing by Smax, using the remainder as your Sindex. Then we divide the quotient by Emax, using the remainder as Eindex. The new quotient is Nindex.
I = Smax * Q + Sindex ( 0 <= Sindex < Smax )
Q = Emax * Q' + Eindex ( 0 <= Eindex < Emax )
Q' = Nindex
Once we've encoded the 13-set, can we get it back easily? With the index 15 from the 3-sets example, we might think it would be okay to just start enumerating them. This is extremely ineffecient, of course, in the case of Nindex where the value is between 0 and 635013559599.
Instead we look first for the largest element, then the next largest, etc. We can find the largest element of our n-set by finding the largest K such that Choose(K,n) is less than (or equal to) Nindex.
For example, in the case of the 15th 3-set, we realize that since Choose(5,3) < 15, all of the 3-sets of {0,1,2,3,4} come before the 3-set which we are seeking. On other hand, the 3-sets which contain a six or higher in them start at index Choose(6,3)=20 > 15. So the largest element of the 15th 3-set must be 5. We then work backwards from there - it's not difficult.
You must use some sort of large-precision package to do these computations, because the numbers we are using are bigger than can normally be stored in the basic types of most programming languages.
My original code was a hasty implementation in C++. using the g++ "Integer" type. It was able to encode and decode 1000 hands in 10 seconds on a SPARCstation LX. The current version is a Perl implementation. I've also got a Java implementation.
Notice that the niceness of the squashed ordering eases our problem, because we only need to write two routines, seq_to_index and index_to_seq. We can then use them on Nindex, Eindex, and Sindex without any other arguments.