dotslash
3/29/2020 - 9:16 PM
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))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