CODEWITHSUNDEEP
python-3.x
user1677907
user1677907

Reputation: 11

Elements in a list are overwritten

I tried to program a function which creates the linear span of a list of independent vectors, but it seems that the last calculated vector overwrites all other elements. I'd be nice if someone could help me fixing it. 

def span_generator(liste,n):
    """function to generate the span of a list of linear independent 
    vectors(in liste) in the n-dimensional vectorspace of a finite 
    field with characteristic 2, returns a list of all elements which 
    lie inside the span"""
    results=[]
    blank=[]
    for i in range(n):
        blank.append(0)
    a=blank
    if len(liste)>1:
        listenwert=liste[-1]
        liste.pop(-1)
        values=span_generator(liste,n)    
        for i in range(2):
            for j in range(len(values)):
                for k in range(n):
                    a[k]=(i*listenwert[k]+values[j][k])%2
                results.append(a)
    else:       
        for i in range(2):
            for j in range(n):
                a[j]=(i*liste[0][j])
            results.append(a)    
    print(results)
    return results

print(span_generator([[1,0],[0,1]],2)) gives following results

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

instead of the expected: [[0,0],[1,0],[0,1],[1,1]]

Edit: I tried to simplify the program with itertools.product, but it didn't solve the problem.

def span_generator(liste):
    n=len(liste[0])
    results=[]
    coeff=list(itertools.product(range(2), repeat=n))
    blank=[]
    for i in range(n):
        blank.append(0)
    for i in range(len(coeff)):
        a=blank
        for j in range(len(coeff[0])):
            for k in range(n):
                a[k]=(a[k]+coeff[i][j]*liste[j][k])%2
        results.append(a)
    return results

Output: span_generator([[0,1],[1,0]]) [[0, 0], [0, 0], [0, 0], [0, 0]] But it should give [[0,0],[0,1],[1,0],[1,1]]

Another example: span_generator([[0,1,1],[1,1,0]]) should give [[0,0,0],[0,1,1],[1,1,0],[1,0,1]] (2=0 since i'm calculating modulo 2)

Upvotes: 1

Views: 69

Answers (1)

Maarten Fabré
Maarten Fabré

Reputation: 7058

Coefficients

You can use itertools.product to generate the coefficients:

n = len(liste[0])
coefficients = itertools.product(range(2), repeat=len(liste))

yields an iterator with this content:

[(0, 0), (0, 1), (1, 0), (1, 1)]

Linear combinations

You can then selectively multiply the results with the transpose of your liste (list(zip(*liste)))

for coeff in coefficients:            
        yield [sum((a * c) for a, c in zip(transpose[i], coeff)) for i in range(n)]

which take for each dimensionality (for i in range(n)) the sum of the products

def span_generator3(liste):
    n = len(liste[0])
    transpose = list(zip(*liste))
    coefficients = itertools.product(range(2), repeat=len(liste))
    for coeff in coefficients:            
        yield [sum((a * c) for a, c in zip(transpose[i], coeff)) % 2 for i in range(n)]

this produces an iterator. If you want the result in a list-form, just can list() on the iterator

Result

list(span_generator3([[1,2],[4,8]]))

output:

[[0, 0], [4, 8], [1, 2], [5, 10]]

Higher dimensions

list(sorted(span_generator3([[1,2, 4],[8, 16, 32], [64, 128, 256]])))

output:

[[0, 0, 0],
 [1, 2, 4],
 [8, 16, 32],
 [9, 18, 36],
 [64, 128, 256],
 [65, 130, 260],
 [72, 144, 288],
 [73, 146, 292]]

Modulo 2

If you want the result modulo 2, that's just adding 2 characters in the right place 

def span_generator3_mod2(liste):
    n = len(liste[0])
    transpose = list(zip(*liste))
    coefficients = itertools.product(range(2), repeat=len(liste))
    # print(list(itertools.product(range(2), repeat=len(liste))))
    for coeff in coefficients:            
        yield [sum((a * c) for a, c in zip(transpose[i], coeff)) % 2 for i in range(n)]

list(span_generator3_mod2([[0,1,1],[1,1,0]])) gives

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

Upvotes: 1

Related Questions