Derangements - Monte Carlo - Multi Card Match

derangements.cpp

#include <random>
#include <map>
#include <vector>
#include <iostream>
#include <iomanip>

unsigned int
Disarrange(
	const unsigned int					aMax,
	std::mt19937&						aGenerator,
	std::uniform_int_distribution<>&	aDistribution)
{
	unsigned int count = 0;

	for (unsigned int i = 0; i < aMax; ++i)
	{
		const int value = aDistribution(aGenerator);
		if (value == i)
		{
			++count;
		}
	}

	return count;
}

int main()
{
	// The only things you need to modify to do different runs
	const unsigned int rolls = 10000000;
	const unsigned int runs = 32;
	const unsigned int layers = 10;

	std::random_device randomDevice;
	std::mt19937 generator(randomDevice());

	std::vector<std::map<unsigned int, double>> results;
	results.resize(layers);
	
	for (unsigned int run = 1; run < runs; ++run)
	{
		std::uniform_int_distribution<> distribution(0, run - 1);

		std::vector<unsigned int> layerCounts;
		layerCounts.resize(layers);

		for (unsigned int i = 0; i < rolls; ++i)
		{
			const unsigned int result = Disarrange(run, generator, distribution);

			for(unsigned int layer = 0; layer < layerCounts.size(); ++layer)
			{
				if (result > layer)
				{
					++layerCounts[layer];
				}
			}
		}

		for (unsigned int layer = 0; layer < results.size(); ++layer)
		{
			auto& result = results[layer];
			result[run] = (layerCounts[layer] / static_cast<double>(rolls));
		}
	}

	for(const auto& layer : results)
	{
		for (const auto& value : layer)
		{
			std::cout << std::fixed << value.second << '\n';
		}

		std::cout << '\n';
	}

	return 0;
}