using System;

/*
 * This code simulates many trials of the random selection of 40 students out of a population
 * of 700, with the goal of seeing how many of the students would be selected twice in a row.
 * 
 * The analytical solution is a hypergeometric distribution.  This code comes pretty close to
 * that, and I might guess that the difference is due to random number generator.
 * 
 * Jeff Borlik
 * 2004 Sep 21
 */


namespace montecarlo1
{
	/// <summary>
	/// Summary description for Class1.
	/// </summary>
	class Simulation1
	{
		/// <summary>
		/// The main entry point for the application.
		/// </summary>
		/// 

		System.Random m_prandom;
		System.Collections.BitArray m_lastmonth;
		int m_num; // number of people
		int m_choices; // number of people chosen per month

		public Simulation1()
		{
			m_num = 700;
			m_choices = 40;
			m_lastmonth = new System.Collections.BitArray(m_num, false);
			m_prandom = new System.Random();
		}


		[STAThread]
		static void Main(string[] args)
		{
			//
			// TODO: Add code to start application here
			//
			Simulation1 pSim = new Simulation1();

			long accumrepeats = 0;
			long numtrials = 0;
         const int NUMBUCKETS = 11; // 0-10
			long [] repeatbuckets = new long[NUMBUCKETS+1]; // +1 for more than NUMBUCKETS repeats

			const long maxtrials = 1000000;

			for (long i = 1; i <= maxtrials; ++i) 
			{
				int repeats = pSim.pickThisMonth();
				accumrepeats += repeats;
				numtrials++;

				if (repeats < (NUMBUCKETS-1)) 
				{
					repeatbuckets[repeats]++;
				} 
				else 
				{
					repeatbuckets[NUMBUCKETS]++;
				}

//				Console.WriteLine("Trial {0}: {1} repeats",i,repeats);
			}

			Console.WriteLine("Trials {0}: Average repeats {1}",numtrials,(double)accumrepeats/numtrials);

			Console.WriteLine("Buckets:");
			for (int ii = 0; ii <= NUMBUCKETS-1; ii++) 
			{
				Console.WriteLine("   {0} Repeats: {1}",ii,(double)repeatbuckets[ii]/numtrials);
			}
			Console.WriteLine("   >{0} Repeats: {1}",NUMBUCKETS-1,(double)repeatbuckets[NUMBUCKETS]/numtrials);

		}

		// Returns the number of repeats
		int pickThisMonth()
		{
			System.Collections.BitArray thismonth = new System.Collections.BitArray(m_num,false);

			int repeats = 0;

			for (int i = 1; i < m_choices; ++i) 
			{
            int iperson;
            do 
            {
               // repeat until we find someone that hasn't already been picked
               iperson = m_prandom.Next(m_num);
            } while (thismonth[iperson]==true);

				thismonth[iperson] = true;
				
				if (m_lastmonth[iperson] == true) 
				{
					repeats++;
				}
			}

			m_lastmonth = thismonth;

			return repeats;
		}
	}
}