Skip to content

Instantly share code, notes, and snippets.

@snovvcrash
Last active July 7, 2017 23:59
Show Gist options
  • Save snovvcrash/b1dce7a5a524cb5919459486de9a21f3 to your computer and use it in GitHub Desktop.
Save snovvcrash/b1dce7a5a524cb5919459486de9a21f3 to your computer and use it in GitHub Desktop.
Bruteforcing secretary problem.
/**
* 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
#
# 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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment