"Ge' Weijers" <[EMAIL PROTECTED]> writes:
> On Wed, Jun 23, 1999 at 12:46:43PM -0500, Matt Crawford wrote:
> > > > > There are 52! bridge hands, so a random hand has
> > > > > log2(56!) = 226 bits of entropy or 68 decimal digits worth.
> > No, just 52! / (13!)^4 hands, which is around 2^96.
> The interesting part is to come up with an algorithm that only uses 96 bits.
Not so hard. Let C(m,n) be the number of ways of choosing n items from
a set of m, unordered.
To choose the first hand there are C(52,13) choices, then to choose the
second hand C(39,13), then to choose the third, C(26,13), and the fourth
is then automatically determined. These will add up to Matt's formula.
The problem thus reduces to choosing one of C(m,n) choices with minimal
number of bits.
To solve it we will assume a random package which can make choices with
specified probability x out of y, where y may not be a power of two,
without wasting bits. Such a system was recently described on coderpunks
under the thread "being miserly with randomness".
To choose one of C(m,n) choices, we first determine whether the first
element will be in the selection. The probability is simply n/m.
After we have done this, the problem reduces to either choosing n-1
elements from m-1 in the case that the first element was chosen, or n
elements from m-1 in the case that it was not chosen. We can therefore
repeat the process to determine whether the second element was selected,
then the third, and so on. Continue to repeat until all n elements are
chosen.
In conjunction with an efficient x out of y interface to the RNG, this
will choose your bridge hands without wasting any random bits.
