Secretary Problem ( A Optimal Stopping Problem ) | Python3 Program to test 1 / e law for Secretary Problem ; To find closest integer of num . ; Finds best candidate using n / e rule . candidate [ ] represents talents of n candidates . ; Calculating sample size for benchmarking . ; Finding best candidate in sample size ; Finding the first best candidate that is better than benchmark set . ; Driver code ; n = 8 candidates and candidate array contains talents of n candidate where the largest number means highest talented candidate . ; generating random numbers between 1 to 8 for talent of candidate
import random NEW_LINE import math NEW_LINE e = 2.71828 ; NEW_LINE def roundNo ( num ) : NEW_LINE INDENT if ( num < 0 ) : NEW_LINE INDENT return ( num - 0.5 ) NEW_LINE DEDENT else : NEW_LINE INDENT return ( num + 0.5 ) ; NEW_LINE DEDENT DEDENT def printBestCandidate ( candidate , n ) : NEW_LINE INDENT sample_size = roundNo ( n / e ) ; NEW_LINE print ( " Sample size is " , math . floor ( sample_size ) ) ; NEW_LINE best = 0 ; NEW_LINE for i in range ( 1 , int ( sample_size ) ) : NEW_LINE INDENT if ( candidate [ i ] > candidate [ best ] ) : NEW_LINE INDENT best = i ; NEW_LINE DEDENT DEDENT for i in range ( int ( sample_size ) , n ) : NEW_LINE INDENT if ( candidate [ i ] >= candidate [ best ] ) : NEW_LINE INDENT best = i ; NEW_LINE break ; NEW_LINE DEDENT DEDENT if ( best >= int ( sample_size ) ) : NEW_LINE INDENT print ( " Best candidate found is " , math . floor ( best + 1 ) , " with ▁ talent " , math . floor ( candidate [ best ] ) ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Couldn ' t ▁ find ▁ a ▁ best ▁ candidate " ) ; NEW_LINE DEDENT DEDENT n = 8 ; NEW_LINE candidate = [ 0 ] * ( n ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT candidate [ i ] = 1 + random . randint ( 1 , 8 ) ; NEW_LINE DEDENT print ( " Candidate ▁ : ▁ " , end = " " ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( ( i + 1 ) , end = " ▁ " ) ; NEW_LINE DEDENT print ( " Talents : " , ▁ end ▁ = ▁ " " ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( candidate [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT printBestCandidate ( candidate , n ) ; NEW_LINE