| My program says the chance of getting 17 or more different cards is
about .00305282, or about one in 328. (This program ignores the size
of the pool, which we can do since it is so large.)
-- edp
#include <stdio.h>
#include <stdlib.h>
typedef int Boolean;
#define TRUE 1
#define FALSE 0
#define MEMORY 0
#define USAGE 1
void panic(int error)
{
switch (error)
{
case MEMORY:
fprintf(stderr, "Out of memory.\n");
break;
case USAGE:
fprintf(stderr, "Usage: count num [limit]\n");
break;
}
exit(1);
}
typedef struct partition
{
int t; /* number of last used element */
int e[1]; /* elements */
} Partition;
Boolean next_partition(Partition **p, int n)
{
int i, limit, sum;
/* If we are passed a null pointer, create and initialization a
partition. */
if (!*p)
{
*p = (Partition *)malloc((n-1)*sizeof(int) + sizeof **p);
if (!*p)
panic(MEMORY);
/* Set up one element containing all the members. */
(*p)->t = 0;
(*p)->e[0] = n;
return TRUE;
}
/* Otherwise, increment the partition we are given to the next
partition. */
for (i = (*p)->t; i >= 0 && (*p)->e[i] == 1; i--)
;
/* If we reached the last partition, free the structure. */
if (i < 0)
{
free((*p));
return FALSE;
}
limit = --(*p)->e[i];
sum = (*p)->t-i + 1;
for (i++; sum; i++)
{
(*p)->e[i] = sum < limit ? sum : limit;
sum -= (*p)->e[i];
}
(*p)->t = i-1;
return TRUE;
}
/* Figure out how many ways this partition pattern can be ordered. */
double num_orders(Partition *p, int n)
{
int i, j;
double num;
num = 1;
for (i = 1; i <= n; i++)
num *= i;
for (i = 0; i <= p->t; i++)
for (j = 1; j <= p->e[i]; j++)
num /= j;
return num;
}
/* Figure out how many ways this partition can be filled with objects. */
double num_fills(Partition *p, int n)
{
double num;
int i, length;
/* Select any type to use for the first bin. */
num = n--;
length = 1;
for (i = 1; i <= p->t; i++)
{
/* The elements in this bin can be chosen from any one
of the types not yet used. */
num *= n--;
/* Is this bin the same size as the previous one? */
if (p->e[i] == p->e[i-1])
/* If so, the bins can be reordered. */
num /= ++length;
else
/* Otherwise, start counting again. */
length = 1;
}
return num;
}
int main(int argc, char *argv[], char *arge[])
{
int i, limit, n;
Partition *p;
double total, subset;
if (argc != 2 && argc != 3)
panic(USAGE);
n = atoi(argv[1]);
if (n <= 0)
panic(USAGE);
limit = argc >= 3 ? atoi(argv[2]) : 0;
for (total = 1, i = 0; i < n; i++)
total *= n;
for (p = NULL, subset = 0; next_partition(&p, n);)
{
#if 0
for (i = 0; i <= p->t; i++)
printf("%d ", p->e[i]);
printf("\n");
#endif
if (p->t >= limit-1)
subset += num_orders(p, n) * num_fills(p, n);
}
printf("Subset = %lg. Total = %lg. Ratio = %lg.\n", subset, total,
subset/total);
}
|
| re .2
I use slightly different calculations and get a probability of around 1 in
327 for a reasonably large pool (say 200000 cards in total). (I would
therefore have to disagree with .1 as to how 'lucky' the base noter
was.)
My program does not handle the partitioning in a flexible manner i.e. I
hard coded the ways in which the non-unique cards are "grouped". I also
don't compute the probabilities exactly but just compute using G-float
to get an approximation.
The program is attached. No prizes for coding style. It was a quick
hack.
/* must compile
$ CC/G_FLOAT x
and link
$ LINK x,CG/OPT
where CG.OPT contains
SYS$LIBRARY:VAXCRTLG/SHARE
*/
#ifndef D
#define D if(0)
#endif
double C( int n, int r )
{
double t = 1;
int i;
if ( r < 0 )
return 0;
else if ( r == 0 )
return 1;
else if ( r > n / 2 )
r = n - r;
for ( i = 0; i < r; i++ )
t *= n-i,
t /= r-i;
return t;
}
double P( int n, int r )
{
double t = 1;
int i;
for ( i = 0; i < r; i++ )
t *= n-i;
return t;
}
double power( int base, int expon )
{
double t = 1;
int i;
D printf("%d ** %d = ",base,expon);
if ( expon <= 0 )
{
D printf("\n");
return 1;
}
for ( i = 0; i < 32; i++ )
{
t *= t;
if ( expon < 0 )
t *= base;
expon <<= 1;
}
D printf("%.15E\n",t);
return t;
}
double nways( int r, int s, int dups )
{
/* number of ways of choosing r from r ranks by s suits where the result is
"dups" duplicates i.e. that many cards not contributing to the set of unique
cards drawn. */
/* P(r,x) or C(r,x) choose the x ranks to be tied up in groups
C(s,dups') indistinguishable ways of choosing a group of dups'
C(r-x,r-dupss) choose the remaining ranks (all unique)
power(s,r-dupss) indistinguishable ways of choosing the unique cards
*/
switch ( dups )
{
case 0:
return power(s,r);
break;
case 1:
/* one pair */
return C(r,1) * C(s,2) * C(r-1,r-2) * power(s,r-2);
break;
case 2:
/* one triple */
return C(r,1) * C(s,3) * C(r-1,r-3) * power(s,r-3) +
/* two pairs */
C(r,2) * C(s,2) * C(s,2) * C(r-2,r-4) * power(s,r-4);
break;
case 3:
/* one four of a kind */
return C(r,1) * C(s,4) * C(r-1,r-4) * power(s,r-4) +
/* three pairs */
C(r,3) * C(s,2) * C(s,2) * C(s,2) * C(r-3,r-6) * power(s,r-6) +
/* a triple and a pair */
P(r,2) * C(s,3) * C(s,2) * C(r-2,r-5) * power(s,r-5);
break;
default:
return 0;
}
}
main(int argc, char*argv[])
{
int r;
int s;
int n;
double d;
double n0,n1,n2,n3;
double sigman;
r = argc > 1? atoi(argv[1]) : 4;
s = argc > 2? atoi(argv[2]) : 5;
n = r * s;
d = C(n,r);
printf("d = %.15E\n",d);
n0 = nways( r, s, 0 );
printf("n0 = %.15E\n",n0);
n1 = nways( r, s, 1 );
printf("n1 = %.15E\n",n1);
n2 = nways( r, s, 2 );
printf("n2 = %.15E\n",n2);
n3 = nways( r, s, 3 );
printf("n3 = %.15E\n",n3);
sigman = n0+n1+n2+n3;
printf("sigma n[i] = %.15E\n",sigman);
printf("prob = %.15E (1 in %d)\n",sigman/d,(int)(d/sigman));
}
|