Subj : Re: combo numbering
To   : comp.programming
From : mensanator@aol.com
Date : Thu Oct 06 2005 04:46 pm


[jongware] wrote:
> <bob@coolgroups.com> wrote in message
> news:1128634092.444124.288010@z14g2000cwz.googlegroups.com...
> >A 52bit number has 4.50359963 =D7 10^15 possibilities, which is way too
> >high.  I'm planning on storing an array of 133,784,560 32 bit numbers
> >in memory, which takes up about 600 mb.  This is on a machine that has
> >only 768 MB of RAM.
>
> You have 52 cards, so you have to use 6 bits (0..63) to identify each card
> (0..12 per card, 2 bits for its color).
> 7 cards use 42 bits -> 5 1/4 byte.
> I don't think there is any way to store information about 52 elements in
> just one 32 bit number! Your 133 mil combinations will therefore need 133
> mil times 5 1/4 bytes of information, thats already 700 MB.
> Actually, first thing I though would be to loose the 1/4 byte and expand =
to
> 6 bytes; then, a natural optimization would be to use 8 bytes and lo and
> behold... you're out of memory.
> How did you arrive on 133 mil? 52*51*50*49*48*47*46 =3D 674,274,182,400.

That's permutations (order significant). Divide that by 7*6*5*4*3*2
to get combinations (order insignificant).


>=20
> [jongware]

.