Bruteforcing secretary problem.

secretary_problem_bruteforce.cpp

/**
 * secretary_problem_bruteforce.cpp
 *
 * Bruteforcing Secretary Problem
 * by snovvcrash
 * 04.2017
 */

/*
 * Calculating running time for n applicants (on current machine)
 * -------------------------------------------------------------------
 * Example:
 * n = 11, runtime ~ 7.5 s (experimentally)
 * n > 11, runtime ~ ((n*n!) / (11*11!)) * 7.5
 * n < 11, runtime ~ ((11*11!) / (n*n!)) * 7.5
 * -------------------------------------------------------------------
 * Some estimations:
 * n = 10, runtime ~ 0.7 s
 * n = 11, runtime ~ 7.5 s
 * n = 12, runtime ~ 100 s
 * n = 13, runtime ~ 0.4 h
 * n = 14, runtime ~ 5.8 h
 * n = 15, runtime ~ 3.9 d
 * ...
 * n = 100, runtime ~ 5 * 10^144 years
 */

#include <iostream>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include "ttmath/ttmathbig.h" // using TTMath library for big numbers: http://www.ttmath.org/
using namespace std;

using BigInt = ttmath::UInt<100>;

BigInt factorial(BigInt n) { return (n == 1 || n == 0) ? 1 : factorial(n-1) * n; }

template<unsigned int size>
int conv_to_double(const ttmath::UInt<size>& in, double& out) {
	ttmath::Big<1, size> temp(in);
	return temp.ToDouble(out);
}

int interview(vector<int>& applicants, vector<BigInt>& numSuccess) {
	if (applicants.size() <= 0)
		return 0;

	for (size_t i = 1; i < applicants.size()-1; ++i) {
		BigInt countSuccess = 0;
		do {
			auto border = applicants.begin();
			advance(border, i);

			int best = *max_element(applicants.begin(), border);

			auto person = border;
			for (person = border; person != applicants.end(); ++person)
				if (best < *person)
					break;
			if (*person == *max_element(applicants.begin(), applicants.end()))
				++countSuccess;
		} while (next_permutation(applicants.begin(), applicants.end()));
		numSuccess[i] = countSuccess;
		// cout << i << endl; // progress
	}

	numSuccess.front() = numSuccess.back() = factorial(applicants.size()-1);

	return 1;
}

int main(int argc, char* argv[]) {
	if (argc != 2) {
		cout << "help: ./a.out <num_of_applicants>" << endl;
		return -1;
	}

	istringstream ss(argv[1]); int x;
	if (!(ss >> x)) {
		cerr << "Invalid input type" << endl;
		return -2;
	}

	vector<int> applicants(x, 0);

	int count = 0;
	generate(applicants.begin(), applicants.end(), [&](){ return ++count; });

	vector<BigInt> numSuccess(x, 0);

	if (interview(applicants, numSuccess)) {
		copy(numSuccess.begin(), numSuccess.end(), std::ostream_iterator<BigInt>(cout, "   "));
		cout << endl;

		// events_success = numSuccess[index_max]
		size_t index_max = 0;
		for (size_t i = 1; i < numSuccess.size(); ++i)
			if (numSuccess[i] > numSuccess[index_max])
				index_max = i;

		BigInt events_possible = factorial(applicants.size());

		double a; double b;
		conv_to_double(numSuccess[index_max], a);
		conv_to_double(events_possible, b);

		cout << "Step: " << index_max + 1 << endl; // skip (step-1) applicants
		cout << "Prob: " << numSuccess[index_max] << "/" << events_possible << " = " << a / b << endl;
	}
	else {
		cout << "Invalid number of applicants" << endl;
		return -3;
	}

	return 0;
}

secretary_problem_bruteforce.py

#
# secretary_problem_bruteforce.py
#
# Bruteforcing Secretary Problem
# by snovvcrash
# 04.2017
#

#
# Calculating running time for n applicants (on current machine)
# -------------------------------------------------------------------
# Example:
# n = 11, runtime ~ 450.0 s (experimentally)
# n > 11, runtime ~ ((n*n!) / (11*11!)) * 450.0
# n < 11, runtime ~ ((11*11!) / (n*n!)) * 450.0
# -------------------------------------------------------------------
# Some estimations:
# n = 10, runtime ~ 37.5  s
# n = 11, runtime ~ 450.0 s
# n = 12, runtime ~ 1.65  h
# n = 13, runtime ~ 23.0  h
# n = 14, runtime ~ 14.5  d
# n = 15, runtime ~ 232.7 d
# ...
# n = 100, runtime ~ 3 * 10^146 years
#

from itertools import permutations
from math      import factorial
from sys       import argv, exit

def Interview(applicants):
	if int(argv[1]) <= 0:
		return 0

	numSuccess = [0] * len(applicants)

	for i in range(1, len(applicants)-1):
		countSuccess = 0
		for perm in permutations(applicants):
			best = max(perm[:i])
			for person in perm[i:]:
				if best < person:
					break
			if person == max(perm):
				countSuccess += 1
		numSuccess[i] = countSuccess
		# print(i) # progress

	numSuccess[0] = numSuccess[-1] = factorial(len(applicants)-1)

	return numSuccess

def main():
	if len(argv) != 2:
		print("help: python3 secretary_problem_bruteforce.py <num_of_applicants>")
		exit(-1)

	try:
		x = int(argv[1])
	except ValueError:
		print("Invalid input type")
		exit(-2)

	applicants = [i for i in range(1, x+1)]

	numSuccess = Interview(applicants)

	if numSuccess != 0:
		print(numSuccess)
		events_success  = max(numSuccess)
		events_possible = factorial(len(applicants))
		print("Step: ", numSuccess.index(events_success)+1) # skip (step-1) applicants
		print("Prob: ", events_success, "/", events_possible, " = ", events_success / events_possible)
	else:
		print("Invalid number of applicants")
		exit(-3)

main()