Mots sans k-repetitions



In [1]:

    
@cached_function
def NRccount(k, n, c):
    if n == 0:
        return 1
    else:    
        if c == 0:
            return NRccount(k, n-1, k-1)
        else:
            return (NRccount(k, n-1, c-1) +
                    NRccount(k, n-1, k-1))
            
@cached_function
def NRcount(k, n):
    if n == 0:
        return 1
    else:
        return 2*NRccount(k, n-1, k-1)



In [2]:

    
[NRcount(2, i) for i in range(10)]









    Out[2]:





[1, 2, 4, 6, 10, 16, 26, 42, 68, 110]

On compare avec le nombre de messages quand il n'y a pas de contrainte:



In [3]:

    
NRcount(2, 100), 2^100









    Out[3]:





(1146295688027634168202, 1267650600228229401496703205376)

Une méthode de rejet serait completement inefficace. Le nombre de messages valides étant très petit devant le nombre de messages non contraints.



In [4]:

    
log(NRcount(2, 100)*1.)/log(2.)









    Out[4]:





69.9574692292487

Le nombre de messages est proche du nombre de message que l'on peut faire passer en utilisant 70 bits non contraints: On perd donc environ 30% de la bande passante si l'on interdit des répétitions de plus de deux lettres consécutives.



In [ ]:



In [ ]:



In [5]:

    
def NRc(k, n, c, i):
    if n == 0:
        yield []
    else:    
        ib = 1-i
        if c == 0:
            for w in NRc(k, n-1, k-1, ib):
                yield [ib]+w
        else:
            for w in NRc(k, n-1, c-1, i):
                yield [i]+w
            for w in NRc(k, n-1, k-1, ib):
                yield [ib]+w
            
def NR(k, n):
    if n == 0:
        yield []
    else:
        for w in NRc(k, n-1, k-1, 0):
            yield [0]+w
        for w in NRc(k, n-1, k-1, 1):
            yield [1]+w



In [6]:

    
list(NR(2, 5))









    Out[6]:





[[0, 0, 1, 1, 0],
 [0, 0, 1, 0, 0],
 [0, 0, 1, 0, 1],
 [0, 1, 1, 0, 0],
 [0, 1, 1, 0, 1],
 [0, 1, 0, 0, 1],
 [0, 1, 0, 1, 1],
 [0, 1, 0, 1, 0],
 [1, 1, 0, 0, 1],
 [1, 1, 0, 1, 1],
 [1, 1, 0, 1, 0],
 [1, 0, 0, 1, 1],
 [1, 0, 0, 1, 0],
 [1, 0, 1, 1, 0],
 [1, 0, 1, 0, 0],
 [1, 0, 1, 0, 1]]



In [7]:

    
[len(list(NR(2, i))) for i in range(10)]









    Out[7]:





[1, 2, 4, 6, 10, 16, 26, 42, 68, 110]



In [ ]:



In [ ]:



In [ ]:



In [ ]:

Pour la culture: la méthode des séries génératrices permet un comptage plus efficace:



In [8]:

    
[NRcount(2, i) for i in range(10)]









    Out[8]:





[1, 2, 4, 6, 10, 16, 26, 42, 68, 110]



In [9]:

    
gf = (1+x+x^2)/(1-x-x^2)



In [10]:

    
gf









    Out[10]:





-(x^2 + x + 1)/(x^2 + x - 1)



In [11]:

    
taylor(gf, x, 0, 20)









    Out[11]:





21892*x^20 + 13530*x^19 + 8362*x^18 + 5168*x^17 + 3194*x^16 + 1974*x^15 + 1220*x^14 + 754*x^13 + 466*x^12 + 288*x^11 + 178*x^10 + 110*x^9 + 68*x^8 + 42*x^7 + 26*x^6 + 16*x^5 + 10*x^4 + 6*x^3 + 4*x^2 + 2*x + 1



In [ ]:



In [ ]: