Instantly share code, notes, and snippets.

# snovvcrash/secretary_problem_bruteforce.cpp

Last active July 7, 2017 23:59
Show Gist options
• Save snovvcrash/b1dce7a5a524cb5919459486de9a21f3 to your computer and use it in GitHub Desktop.
Bruteforcing secretary problem.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /** * 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 #include #include #include #include #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 int conv_to_double(const ttmath::UInt& in, double& out) { ttmath::Big<1, size> temp(in); return temp.ToDouble(out); } int interview(vector& applicants, vector& 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 " << endl; return -1; } istringstream ss(argv[1]); int x; if (!(ss >> x)) { cerr << "Invalid input type" << endl; return -2; } vector applicants(x, 0); int count = 0; generate(applicants.begin(), applicants.end(), [&](){ return ++count; }); vector numSuccess(x, 0); if (interview(applicants, numSuccess)) { copy(numSuccess.begin(), numSuccess.end(), std::ostream_iterator(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; }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # # 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 ") 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()