Quote:
Originally Posted by Pyromantha
Sorry, maybe missing something but doesn't that use more than 226 bits to encode a deck? It seems like it uses even more than the naive 249 bit method.
Just so we're on the same page, suppose my shuffled deck is the exact reverse of the ordered deck. The ordered deck goes 2c,....Ac,2d,....,Ad,2h,....,Ah,2s,.....As for the sake of argument. 2c is card 1, As is card 52 = 110100 in binary.
I look at my first card, its the As.
V+52 = 52, multiply by M = 2704, decrement M to 51. Next card is Ks, card 51, 2704+51 = 2755 * 51 = 140505. The end number is going to be bigger than 52!, so bigger than 2^226, and likely much bigger...
For a deck of four cards, 4321 is encoded as 119 which is 7 bits in binary, whereas 4 card decks can theoretically be encoded in 5 bits as 4! = 24 < 32.
Sorry, I missed this when it was posted.
Yes, I think you are missing something: probably because you are encoding the cards using 1 -> 52, rather than 0 -> 51, and you are needlessly encoding the final card.
I'm in a bit of a hurry at the moment so I don't have time to double check but here's a code snipet I quickly created to implement the encoding algorithm described and its output.
The cards are numbered 0 to 51 and, as there is only one possibility for the last card it is not implicitly encoded.
Code:
int n = 51 ;
double v = 0 ;
while ( n > 0 )
{
v = v + n ;
v *= n ;
TRACE( "Encoded %d current V = %9.3g\n", n, v ) ;
n -- ;
}
Encoded 51 current V = 51
Encoded 50 current V = 2.65e+003
Encoded 49 current V = 1.33e+005
Encoded 48 current V = 6.5e+006
Encoded 47 current V = 3.12e+008
Encoded 46 current V = 1.47e+010
Encoded 45 current V = 6.74e+011
Encoded 44 current V = 3.03e+013
Encoded 43 current V = 1.34e+015
Encoded 42 current V = 5.74e+016
Encoded 41 current V = 2.41e+018
Encoded 40 current V = 9.89e+019
Encoded 39 current V = 3.95e+021
Encoded 38 current V = 1.54e+023
Encoded 37 current V = 5.86e+024
Encoded 36 current V = 2.17e+026
Encoded 35 current V = 7.81e+027
Encoded 34 current V = 2.73e+029
Encoded 33 current V = 9.29e+030
Encoded 32 current V = 3.07e+032
Encoded 31 current V = 9.81e+033
Encoded 30 current V = 3.04e+035
Encoded 29 current V = 9.12e+036
Encoded 28 current V = 2.65e+038
Encoded 27 current V = 7.41e+039
Encoded 26 current V = 2e+041
Encoded 25 current V = 5.2e+042
Encoded 24 current V = 1.3e+044
Encoded 23 current V = 3.12e+045
Encoded 22 current V = 7.18e+046
Encoded 21 current V = 1.58e+048
Encoded 20 current V = 3.32e+049
Encoded 19 current V = 6.63e+050
Encoded 18 current V = 1.26e+052
Encoded 17 current V = 2.27e+053
Encoded 16 current V = 3.86e+054
Encoded 15 current V = 6.17e+055
Encoded 14 current V = 9.25e+056
Encoded 13 current V = 1.3e+058
Encoded 12 current V = 1.68e+059
Encoded 11 current V = 2.02e+060
Encoded 10 current V = 2.22e+061
Encoded 9 current V = 2.22e+062
Encoded 8 current V = 2e+063
Encoded 7 current V = 1.6e+064
Encoded 6 current V = 1.12e+065
Encoded 5 current V = 6.72e+065
Encoded 4 current V = 3.36e+066
Encoded 3 current V = 1.34e+067
Encoded 2 current V = 4.03e+067
Encoded 1 current V = 8.07e+067
Which is ~= 52!
If there are any further problems I'll look at it in more detail.