hat.c

Simulation Modeling,Discrete Event Simulation,Statistical Analysis of Simulation Models

/* ---------------------------------------------------------------------- * 
 * A Monte Carlo simulation of the hat check girl problem.                *
 *                                                                        * 
 * Name              : hat.c                                              * 
 * Authors           : Steve Park & Dave Geyer                            * 
 * Language          : ANSI C                                             * 
 * Latest Revision   : 09-16-95                                           * 
 * Compile with      : gcc hat.c rng.c                                    *
 * ---------------------------------------------------------------------- */

#include <stdio.h>
#include "rng.h"

#define  SIZE  10                            /* array size                */
#define  N     10000L                        /* number of replications    */

typedef long permutation[SIZE];

/* global variables */
long         i;                              /* replication index         */
permutation  arr;                            /* array                     */
long         count = 0;                      /* # of times a match occurs */
double       p;                              /* probability estimate      */

/* =============================== */
  long Equilikely(long a, long b)            /* use a < b                 */
/* =============================== */
{
  return(a + (long) ((b - a + 1) * Random()));
}

/* ============================== */
  void Initialize(permutation a)
/* ============================== */
{
  int j;

  for(j = 0; j < SIZE; j++)
    a[j] = j;
}

/* =========================== */
  void Shuffle(permutation a)
/* =========================== */
{ 
  int j;
  int t;
  int hold;

  for(j = 0; j < (SIZE - 1); j++) {          /* shuffle an array         */
    t     = Equilikely(j, (SIZE - 1));       /* in such a way that all   */
    hold  = a[j];                            /* permutations are equally */
    a[j]  = a[t];                            /* likely to occur          */
    a[t]  = hold;
  }
}

/* ============================ */
  int Check(permutation a)
/* ============================ */
{ 
  int j    = 0;
  int test = 0;

  do {                                       /* test to see if at least */
    test = (a[j] == j);                      /* one element is in its   */
    j++;                                     /* 'natural' position      */
  } while ((j != SIZE) && !test);            /* - return a 1 if so      */
  return (test ? 1 : 0);                     /* - return a 0 otherwise  */
}

/* ============== */
  int main(void)
/* ============== */
{
  PutSeed(0);

  Initialize(arr);

  for(i = 0; i < N; i++) {                 /* do N Monte Carlo replications */
    Shuffle(arr);
    count += Check(arr);
  }

  p = (double) (N - count) / (double) N;   /* estimate the probability */

  printf("\nfor %ld replications and an array of size %d\n", N, SIZE);
  printf("the estimated probability is %5.3lf\n\n", p);

  return(0);
}