Re: [HOE] Job's done!

[Matt Crawford <matt@severian.chi.il.us>]

> Well, I've finished Card Dealer.  I figured out how to do some
> checking to see if a card's been drawn already, and while it's not
> perfect (it's a 10,000 check loop), it does now reduce the chance
> of a repeat draw to negligible levels.  It can be downloaded at ...

I don't understand this fuss about 10,000 iterations to check whether
you're dealing the same card twice.  You simply have to generate the
deck as an array of 54 cards, then pass through the array once
swapping each card with the one in a randomly-chosen position.  Then
you're ready to deal.  I can't run your program to see any trouble
because it's dos/windows-only and you didn't provide the source.
(Any reason why not?)

What's more, you don't even have to use 54 random numbers to shuffle.
(Although that would probably be the most straightforward to code.)
If you have a source of random numbers with a range greater than the
total number of possible subsets of "m" cards chosen from 54 (which
requires 64 bit arithmetic if you're going to deal, say, 12 cards
from 54), you can pick a random n in the range 1 to "54-choose-m" and
generate the n'th subset in an algorithmic fashion:

/*
 * Choose the k'th subset of N integers from the set
 * { 0, 1, ... M-1 }.  For each k from 0 to C(M, N),
 * a different subset is returned.  Therefore, every
 * possible such subset is generated for 0 <= k <= C(M, N).
 *
 * C(m, n) denotes "m choose n", or m!/[n! (m-n)!].
 *
 *
 * Author: Matt Crawford, 28 August 1997.
 */


typedef unsigned int            uint;
typedef unsigned long long      ull;

/* calculate C(m, n) = m! / [n! (m-n)!] */
static ull
choose(uint m, uint n)
{
  ull   c = m;
  uint  i = m-n, j = 2;
  if ( n > m )
    return 0;                   /* error! */
  if ( i > n )
    i = n;
  if ( i == 0 )
    return 1;
  for ( ; j <= i; j++ ) {
    c *= (--m);
    c /= j;
  }
  return c;
}

/* The actual work happens here.  subset() is the interface to subset1() */
/* The basis of the algorithm is that, of the c=C(n-o,m-o) subsets of
 * size n-o of the set {o, o+1, ..., m-1}, ((n-o)/(m-o))*c of them contain o
 * and the rest don't.  Start with o=0 and recurse.
 */
static void
subset1(uint *S, uint o, uint M, uint N, ull k, ull c)
{
  c *= N;
  c /= M;
  if ( k < c ) {
    *S = o;
    if ( N > 1 )
      subset1(S+1, o+1, M-1, N-1, k, c);
  } else
    subset1(S, o+1, M-1, N, k-c, (M-N)*c/N);
}

/*
 * return the selected subset in S[0] .. S[N-1]
 * and 0 on success, -1 on error
 */
int
subset(uint *S, uint M, uint N, ull k)
{
  ull   c = choose(M, N);
  if ( k >= c )                 /* also catches range error on (M, N) */
    return -1;
  subset1(S, 0, M, N, k, c);
  return 0;
}