exp_wait_for_perm.py

# Usage:
# > python exp_wait_for_perm.py 12
# > python exp_wait_for_perm.py 3 
# Needs - numpy

from numpy.random import seed
from numpy.random import randint
from collections import defaultdict as ddict 
import sys
import time


# You repeatedly pick a random number from 1 to N. How long until you’ll hit a consecutive sequence 
# of N with no repetitions (that is, a permutation of {1, ..., N})?
N = int(sys.argv[1]) 
# For bigger N, use a bigger SAMPLE_SIZE
# - 20 million is good for N=12
# - 1 million is good for upto N=5
SAMPLE_SIZE = 1000*1000
if N > 8:
    SAMPLE_SIZE = 1000*1000*10
if N > 10:
    SAMPLE_SIZE = 1000*1000*20

# seed random number generator
seed(int(time.time()) % 100000)
# from [1, N+1) => [1, N]
values = randint(1, N+1, SAMPLE_SIZE)
print(values[:100]) # Sanity check


cur_numbers = ddict(int)
success = 0
for i in range(SAMPLE_SIZE):
    if i >= N:
        to_rem = values[i-N]
        to_rem_cnt = cur_numbers[to_rem]
        if to_rem_cnt > 1:
            cur_numbers[to_rem] -= 1
        elif to_rem_cnt == 1:
            del cur_numbers[to_rem]
        else:
            print(cur_numbers)
            print('madness')
            sys.exit(1)

    cur_numbers[values[i]] += 1
    if len(cur_numbers) == N:
        success += 1

FAILS_PER_SUCCESS = ((SAMPLE_SIZE*1.0 - success)/success)
print('''
FAILS_PER_SUCCESS = x => 
The average case is that you need a sequence of x + N numbers to get a a permutation of N towards the end''')
print('FAILS_PER_SUCCESS {}'.format(FAILS_PER_SUCCESS))

zzz_readme.md

Running for 2...12

for N in {2..12}
do
    echo ">>>>>>>RUNNING: python exp_wait_for_perm.py $N"
    python exp_wait_for_perm.py $N
    python exp_wait_for_perm.py $N
    python exp_wait_for_perm.py $N
done

OUTPUT

>>>>>>>RUNNING: python exp_wait_for_perm.py 2
For N=2 FAILS_PER_SUCCESS=0.9994881310384541
For N=2 FAILS_PER_SUCCESS=1.0007722981070692
For N=2 FAILS_PER_SUCCESS=1.0012647993531911
>>>>>>>RUNNING: python exp_wait_for_perm.py 3
For N=3 FAILS_PER_SUCCESS=3.5058237772320724
For N=3 FAILS_PER_SUCCESS=3.4899828482655195
For N=3 FAILS_PER_SUCCESS=3.49796017506061
>>>>>>>RUNNING: python exp_wait_for_perm.py 4
For N=4 FAILS_PER_SUCCESS=9.663936698871755
For N=4 FAILS_PER_SUCCESS=9.62439573749243
For N=4 FAILS_PER_SUCCESS=9.645659232447969
>>>>>>>RUNNING: python exp_wait_for_perm.py 5
For N=5 FAILS_PER_SUCCESS=25.06066923798603
For N=5 FAILS_PER_SUCCESS=25.230884243107834
For N=5 FAILS_PER_SUCCESS=24.943029108078658
>>>>>>>RUNNING: python exp_wait_for_perm.py 6
For N=6 FAILS_PER_SUCCESS=63.678869413362655
For N=6 FAILS_PER_SUCCESS=63.5577792123951
For N=6 FAILS_PER_SUCCESS=64.64695069914002
>>>>>>>RUNNING: python exp_wait_for_perm.py 7
For N=7 FAILS_PER_SUCCESS=161.60162601626016
For N=7 FAILS_PER_SUCCESS=163.2845408247084
For N=7 FAILS_PER_SUCCESS=167.23687752355318
>>>>>>>RUNNING: python exp_wait_for_perm.py 8
For N=8 FAILS_PER_SUCCESS=390.08330074305826
For N=8 FAILS_PER_SUCCESS=431.52595155709344
For N=8 FAILS_PER_SUCCESS=418.81528127623847
>>>>>>>RUNNING: python exp_wait_for_perm.py 9
For N=9 FAILS_PER_SUCCESS=1057.7612493382742
For N=9 FAILS_PER_SUCCESS=1056.4177857671566
For N=9 FAILS_PER_SUCCESS=1066.2358591248667
>>>>>>>RUNNING: python exp_wait_for_perm.py 10
For N=10 FAILS_PER_SUCCESS=2746.252747252747
For N=10 FAILS_PER_SUCCESS=2750.78866263071
For N=10 FAILS_PER_SUCCESS=2714.177844148792
>>>>>>>RUNNING: python exp_wait_for_perm.py 11
For N=11 FAILS_PER_SUCCESS=6855.359273225917
For N=11 FAILS_PER_SUCCESS=7240.129616220131
For N=11 FAILS_PER_SUCCESS=6994.607067879636
>>>>>>>RUNNING: python exp_wait_for_perm.py 12
For N=12 FAILS_PER_SUCCESS=18883.23701605288
For N=12 FAILS_PER_SUCCESS=18171.48087431694
For N=12 FAILS_PER_SUCCESS=18532.177942539387