Distance distribution

dists.ipynb

import matplotlib.pyplot as plt
import numpy as np
import networkx as nx
import pandas as pd
import random

def random_interleaving(a, b):
    """ Generate a random interleaving for sequences a and b"""
    if len(a) == 0 or len(b) == 0:
        return a + b

    if random.randint(1, 2) == 1:
        return [a[0]] + random_interleaving(a[1:], b)
    else:
        return [b[0]] + random_interleaving(b[1:], a)

def gen_lod(balance=60, s=100, N=10000, skip=lambda x:False):
    lod = []
    for i in range(N):
        sa = ['a' + str(i) for i in range(balance)]
        sb = ['b' + str(i) for i in range(s - balance)]
        run = random_interleaving(sa, sb)
        if skip(run):
           continue
        lod.append(count_dist(run))
    return lod

def count_dist(a):
    dists = dict()
    for i, si in enumerate(a):
        for j, sj in enumerate(a):
            if i == j:
                continue
            if si[0] != sj[0]:
                continue
            if i > j:
                continue
            d = j - i
            if d not in dists:
                dists[d] = 0
            dists[d] += 1
    return dists
m = dict({i: 0 for i in range(100)})
for l in gen_lod():
    for i in l:
        m[i] += l[i]
print(sum([k*k*v for k,v in m.items()])/sum([k*v for k,v in m.items()]))
plt.bar(list(m.keys()), [i*m[i] for i in m])
plt.show()