notebook.community

Edit and run

Code de Gray pour les mots binaires





In [1]:



    


def listGray(n):
    if n == 0:
        return [[]]
    else:
        rec = listGray(n-1)
        return [[0] + b for b in rec] + [[1] + b for b in rec[::-1]]



    











In [2]:



    


listGray(1)



    


















    
Out[2]:








[[0], [1]]

















In [3]:



    


listGray(2)



    


















    
Out[3]:








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

















In [4]:



    


listGray(3)



    


















    
Out[4]:








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

















In [5]:



    


listGray(4)



    


















    
Out[5]:








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

Affichage du nombre, de l'ecriture binaire et du code gray correspondant





In [6]:



    


N = 5
[(i, ZZ(i).digits(2, padto=N)[::-1], v) 
 for i, v in enumerate(listGray(N))]



    


















    
Out[6]:








[(0, [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]),
 (1, [0, 0, 0, 0, 1], [0, 0, 0, 0, 1]),
 (2, [0, 0, 0, 1, 0], [0, 0, 0, 1, 1]),
 (3, [0, 0, 0, 1, 1], [0, 0, 0, 1, 0]),
 (4, [0, 0, 1, 0, 0], [0, 0, 1, 1, 0]),
 (5, [0, 0, 1, 0, 1], [0, 0, 1, 1, 1]),
 (6, [0, 0, 1, 1, 0], [0, 0, 1, 0, 1]),
 (7, [0, 0, 1, 1, 1], [0, 0, 1, 0, 0]),
 (8, [0, 1, 0, 0, 0], [0, 1, 1, 0, 0]),
 (9, [0, 1, 0, 0, 1], [0, 1, 1, 0, 1]),
 (10, [0, 1, 0, 1, 0], [0, 1, 1, 1, 1]),
 (11, [0, 1, 0, 1, 1], [0, 1, 1, 1, 0]),
 (12, [0, 1, 1, 0, 0], [0, 1, 0, 1, 0]),
 (13, [0, 1, 1, 0, 1], [0, 1, 0, 1, 1]),
 (14, [0, 1, 1, 1, 0], [0, 1, 0, 0, 1]),
 (15, [0, 1, 1, 1, 1], [0, 1, 0, 0, 0]),
 (16, [1, 0, 0, 0, 0], [1, 1, 0, 0, 0]),
 (17, [1, 0, 0, 0, 1], [1, 1, 0, 0, 1]),
 (18, [1, 0, 0, 1, 0], [1, 1, 0, 1, 1]),
 (19, [1, 0, 0, 1, 1], [1, 1, 0, 1, 0]),
 (20, [1, 0, 1, 0, 0], [1, 1, 1, 1, 0]),
 (21, [1, 0, 1, 0, 1], [1, 1, 1, 1, 1]),
 (22, [1, 0, 1, 1, 0], [1, 1, 1, 0, 1]),
 (23, [1, 0, 1, 1, 1], [1, 1, 1, 0, 0]),
 (24, [1, 1, 0, 0, 0], [1, 0, 1, 0, 0]),
 (25, [1, 1, 0, 0, 1], [1, 0, 1, 0, 1]),
 (26, [1, 1, 0, 1, 0], [1, 0, 1, 1, 1]),
 (27, [1, 1, 0, 1, 1], [1, 0, 1, 1, 0]),
 (28, [1, 1, 1, 0, 0], [1, 0, 0, 1, 0]),
 (29, [1, 1, 1, 0, 1], [1, 0, 0, 1, 1]),
 (30, [1, 1, 1, 1, 0], [1, 0, 0, 0, 1]),
 (31, [1, 1, 1, 1, 1], [1, 0, 0, 0, 0])]

















In [ ]:



    






    











In [ ]:

Iterateur pour code Gray Binaire





In [7]:



    


def binaryIterGray(n):
    gr  = [0]*n
    pos = range(n+1)
    yield gr
    while pos[0] != n:
        i = pos[0]
        gr[i] = 1 - gr[i]
        pos[0] = 0
        pos[i] = pos[i+1]
        pos[i+1] = i+1
        yield gr



    











In [8]:



    


for gr in binaryIterGray(4):
    print gr



    


















    






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

Remarque: dans l'affichage précédent, les poids faibles sont à gauche. Voici la liste dans l'ordre naturel:





In [9]:



    


for gr in binaryIterGray(4):
    print gr[::-1]



    


















    






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

Attention, il faut copier la liste

Pour avoir une complexite optimale, l'itérateur travaille en place sur la liste. Si l'on veut la stocker, il faut en faire une copie:





In [10]:



    


[l for l in binaryIterGray(3)] #bug



    


















    
Out[10]:








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

Version correcte





In [11]:



    


[list(l) for l in binaryIterGray(3)]



    


















    
Out[11]:








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

Version instrumentée avec affichage du tableau des positions





In [14]:



    


def binaryIterGrayInst(n):
    gr  = [0]*n
    pos = range(n+1)
    c   = 0
    yield gr
    while pos[0] != n:
        i = pos[0]
        print (c.digits(2, padto=n)[::-1], 
               pos[n-1::-1], i, gr[::-1])
        c += 1
        gr[i] = 1 - gr[i]
        pos[0] = 0
        pos[i] = pos[i+1]
        pos[i+1] = i+1
        yield gr  ### Version instrumentée



    











In [ ]:



    






    











In [15]:



    


l = list(binaryIterGrayInst(4))



    


















    






([0, 0, 0, 0], [3, 2, 1, 0], 0, [0, 0, 0, 0])
([0, 0, 0, 1], [3, 2, 1, 1], 1, [0, 0, 0, 1])
([0, 0, 1, 0], [3, 2, 2, 0], 0, [0, 0, 1, 1])
([0, 0, 1, 1], [3, 2, 1, 2], 2, [0, 0, 1, 0])
([0, 1, 0, 0], [3, 3, 1, 0], 0, [0, 1, 1, 0])
([0, 1, 0, 1], [3, 3, 1, 1], 1, [0, 1, 1, 1])
([0, 1, 1, 0], [3, 2, 3, 0], 0, [0, 1, 0, 1])
([0, 1, 1, 1], [3, 2, 1, 3], 3, [0, 1, 0, 0])
([1, 0, 0, 0], [4, 2, 1, 0], 0, [1, 1, 0, 0])
([1, 0, 0, 1], [4, 2, 1, 1], 1, [1, 1, 0, 1])
([1, 0, 1, 0], [4, 2, 2, 0], 0, [1, 1, 1, 1])
([1, 0, 1, 1], [4, 2, 1, 2], 2, [1, 1, 1, 0])
([1, 1, 0, 0], [3, 4, 1, 0], 0, [1, 0, 1, 0])
([1, 1, 0, 1], [3, 4, 1, 1], 1, [1, 0, 1, 1])
([1, 1, 1, 0], [3, 2, 4, 0], 0, [1, 0, 0, 1])

















In [ ]:

permutations

Voir https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm





In [16]:



    


def Changes(n):
    if n < 1:
        return
    up = range(n-1)
    down = range(n-2,-1,-1)
    recur = Changes(n-1)
    while True:
        for x in down:
            yield x
        yield next(recur) + 1
        for x in up:
            yield x
        yield next(recur)

def SJT(x):
    try:
        perm = list(x)
    except:
        perm = list(range(x))
    n = len(perm)


    yield perm
    for x in Changes(n):
        perm[x],perm[x+1] = perm[x+1],perm[x]
        yield perm



    











In [17]:



    


list(Changes(1))



    


















    
Out[17]:








[]

















In [18]:



    


list(Changes(2))



    


















    
Out[18]:








[0]

















In [19]:



    


list(Changes(3))



    


















    
Out[19]:








[1, 0, 1, 0, 1]

















In [20]:



    


list(Changes(4))



    


















    
Out[20]:








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

















In [21]:



    


L = [list(p) for p in SJT([1,2,3,4])]
L



    


















    
Out[21]:








[[1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 4, 2, 3],
 [4, 1, 2, 3],
 [4, 1, 3, 2],
 [1, 4, 3, 2],
 [1, 3, 4, 2],
 [1, 3, 2, 4],
 [3, 1, 2, 4],
 [3, 1, 4, 2],
 [3, 4, 1, 2],
 [4, 3, 1, 2],
 [4, 3, 2, 1],
 [3, 4, 2, 1],
 [3, 2, 4, 1],
 [3, 2, 1, 4],
 [2, 3, 1, 4],
 [2, 3, 4, 1],
 [2, 4, 3, 1],
 [4, 2, 3, 1],
 [4, 2, 1, 3],
 [2, 4, 1, 3],
 [2, 1, 4, 3],
 [2, 1, 3, 4]]

















In [22]:



    


[L[4*i:4*i+4] for i in range(6)]



    


















    
Out[22]:








[[[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [4, 1, 2, 3]],
 [[4, 1, 3, 2], [1, 4, 3, 2], [1, 3, 4, 2], [1, 3, 2, 4]],
 [[3, 1, 2, 4], [3, 1, 4, 2], [3, 4, 1, 2], [4, 3, 1, 2]],
 [[4, 3, 2, 1], [3, 4, 2, 1], [3, 2, 4, 1], [3, 2, 1, 4]],
 [[2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 3, 1], [4, 2, 3, 1]],
 [[4, 2, 1, 3], [2, 4, 1, 3], [2, 1, 4, 3], [2, 1, 3, 4]]]

















In [ ]:



    






    











In [ ]:

Content source: hivert/CombiFIIL

Similar notebooks:

notebook.community | gallery | about