0

I am creating a list by shifting an old list out_g, item by item, and appending the result to the new one, new_sets. As I am iterating, I check the resulting shift, and it is correct. After this is complete, I print out the new list, and it is all a single object repeated. What am I missing?

The error occurs during the for loop at the end, where I append the results to new_sets.

#!/usr/bin/python
import math

def LFSR(register, feedback, output):
    """
    https://natronics.github.io/blag/2014/gps-prn/
    :param list feedback: which positions to use as feedback (1 indexed)
    :param list output: which positions are output (1 indexed)
    :returns output of shift register:

    """

    # calculate output
    out = [register[i-1] for i in output]
    if len(out) > 1:
        out = sum(out) % 2
    else:
        out = out[0]

    # modulo 2 add feedback
    fb = sum([register[i-1] for i in feedback]) % 2

    # shift to the right
    for i in reversed(range(len(register[1:]))):
        register[i+1] = register[i]

    # put feedback in position 1
    register[0] = fb

    return out

def shiftInPlace(l, n):
    # https://stackoverflow.com/questions/2150108/efficient-way-to-shift-a-list-in-python
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l

##########
## Main ##
##########
n = 3
# init register states
if n == 5 :
    LFSR_A = [1,1,1,1,0]
    LFSR_B = [1,1,1,0,1]
    LFSR_A_TAPS =[5,4,3,2]
    LFSR_B_TAPS =[5,3]
elif n == 7:
    LFSR_A = [1,0,0,1,0,1,0]
    LFSR_B = [1,0,0,1,1,1,0]
    LFSR_A_TAPS = [7,3,2,1]
    LFSR_B_TAPS = [7,3]
elif n == 3:
    LFSR_A = [1,0,1]
    LFSR_B = [0,1,1]
    LFSR_A_TAPS = [3,2]
    LFSR_B_TAPS = [3,1]

output_reg = [n]
N = 2**n-1
out_g = []
for i in range(0,N): #replace N w/ spread_fact
    a = (LFSR(LFSR_A, LFSR_A_TAPS, output_reg))
    b = (LFSR(LFSR_B, LFSR_B_TAPS, output_reg))
    out_g.append(a ^ b)

# FOR BALANCED GOLD CODES NUMBER OF ONES MUST BE ONE MORE THAN NUMBER
# OF ZEROS 
nzeros = sum(x == 0 for x in out_g)
nones  = sum(x == 1 for x in out_g)
print "Gold Code Output Period[%d] of length %d -- {%d} 0's, {%d} 1's" % (N,N,nzeros,nones)

# produce all time shifted versions of the code
new_sets = []
for i in range(0,N-1):
    new_sets.append(shiftInPlace(out_g,1))
    # a=shiftInPlace(out_g,1)
    # new_sets.append(a)
    print new_sets[i]

print new_sets

My output : 

Gold Code Output Period[7] of length 7 -- {3} 0's, {4} 1's
[1, 1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 0, 1]
[0, 1, 0, 1, 0, 1, 1]
[1, 0, 1, 0, 1, 1, 0]
[0, 1, 0, 1, 1, 0, 1]
[1, 0, 1, 1, 0, 1, 0]
[[1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0]]

Correct values are printing on the iteration, but the final list has all the same values.

Prune
  • 76,765
  • 14
  • 60
  • 81
gutelfuldead
  • 562
  • 4
  • 22

3 Answers3

4

The problem should be obvious from your output - you are seeing the same list because you are appending the same list. Consider - you even name your function "shift in place", so that returns a mutated version of the same list you passed in, and then you append that same list. So one quick fix is to make a copy which you end up appending:

new_sets = []
for i in range(0,N-1):
    new_sets.append(shiftInPlace(out_g,1)[:]) # append copy
    # a=shiftInPlace(out_g,1)
    # new_sets.append(a)
    print new_sets[i]

This gives the output:

Gold Code Output Period[7] of length 7 -- {3} 0's, {4} 1's
[1, 1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 0, 1]
[0, 1, 0, 1, 0, 1, 1]
[1, 0, 1, 0, 1, 1, 0]
[0, 1, 0, 1, 1, 0, 1]
[1, 0, 1, 1, 0, 1, 0]
[[1, 1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 0, 1], [0, 1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 1, 0, 1], [1, 0, 1, 1, 0, 1, 0]]

As an aside, for efficient in-place rotations, consider changing your data-structure to a collections.deque, which implements a doubly-linked list:

In [10]: from collections import deque
    ...: d = deque([1, 1, 0, 1, 0, 1, 0])
    ...: print(d)
    ...: for i in range(0, N-1):
    ...:     d.rotate(-1)
    ...:     print(d)
    ...:
deque([1, 1, 0, 1, 0, 1, 0])
deque([1, 0, 1, 0, 1, 0, 1])
deque([0, 1, 0, 1, 0, 1, 1])
deque([1, 0, 1, 0, 1, 1, 0])
deque([0, 1, 0, 1, 1, 0, 1])
deque([1, 0, 1, 1, 0, 1, 0])
deque([0, 1, 1, 0, 1, 0, 1])
juanpa.arrivillaga
  • 88,713
  • 10
  • 131
  • 172
  • @gutelfuldead make sure you check out the edit that suggests using `collections.deque` instead of `list` – juanpa.arrivillaga Aug 17 '17 at 17:19
  • In case that's not clear ... When you append in this fashion, you append a *reference* to the in-place list. Your two-line code with variable **a** works the same way. You've appended 6 copies of the same variable reference; every time you shift the list, you shift the underlying object. All of the appended references point to that object. – Prune Aug 17 '17 at 17:19
  • @Prune variable *a*? Sorry, I am not sure what you are trying to say... – juanpa.arrivillaga Aug 17 '17 at 17:20
  • I used the code he commented out for more detailed tracing. See the answer I posted ... once he (correctly) accepted yours. – Prune Aug 17 '17 at 17:23
  • @Prune aha! I totally ignored the commented out code :) – juanpa.arrivillaga Aug 17 '17 at 17:24
  • Thank you both. I see the error I was making and understand the cause now. – gutelfuldead Aug 17 '17 at 17:25
  • 1
    Congratulations -- your mental parser is working in that respect. – Prune Aug 17 '17 at 17:25
2

You might try creating your list of rotations like this:

>>> li=[1,0,1,1,0,0]
>>> [li[r:]+li[:r] for r in range(len(li))]
[[1, 0, 1, 1, 0, 0], [0, 1, 1, 0, 0, 1], [1, 1, 0, 0, 1, 0], [1, 0, 0, 1, 0, 1], [0, 0, 1, 0, 1, 1], [0, 1, 0, 1, 1, 0]]
dawg
  • 98,345
  • 23
  • 131
  • 206
2

... following up on my comment to juanpa's answer ...

When you append in this fashion, you append a reference to the in-place list. Your two-line code with variable a works the same way. You've appended 6 copies of the same variable reference; every time you shift the list, you shift the underlying object. All of the appended references point to that object.

Here's detailed output tracing your program. Note how all of the elements of new_sets change on every iteration. In my repair, I used the two-line assignment, but added a copy like this: new_sets.append(a[:])

Gold Code Output Period[7] of length 7 -- {3} 0's, {4} 1's
TRACE out_g = [0, 1, 1, 0, 1, 0, 1]
ENTER shiftInPlace, l= [0, 1, 1, 0, 1, 0, 1]
LEAVE shiftInPlace, head= [0]   l= [1, 1, 0, 1, 0, 1, 0]
TRACE a= [1, 1, 0, 1, 0, 1, 0]  new_sets= [[1, 1, 0, 1, 0, 1, 0]] 

TRACE out_g = [1, 1, 0, 1, 0, 1, 0]
ENTER shiftInPlace, l= [1, 1, 0, 1, 0, 1, 0]
LEAVE shiftInPlace, head= [1]   l= [1, 0, 1, 0, 1, 0, 1]
TRACE a= [1, 0, 1, 0, 1, 0, 1]  new_sets= [[1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1]] 

TRACE out_g = [1, 0, 1, 0, 1, 0, 1]
ENTER shiftInPlace, l= [1, 0, 1, 0, 1, 0, 1]
LEAVE shiftInPlace, head= [1]   l= [0, 1, 0, 1, 0, 1, 1]
TRACE a= [0, 1, 0, 1, 0, 1, 1]  new_sets= [[0, 1, 0, 1, 0, 1, 1], [0, 1, 0, 1, 0, 1, 1], [0, 1, 0, 1, 0, 1, 1]] 

TRACE out_g = [0, 1, 0, 1, 0, 1, 1]
ENTER shiftInPlace, l= [0, 1, 0, 1, 0, 1, 1]
LEAVE shiftInPlace, head= [0]   l= [1, 0, 1, 0, 1, 1, 0]
TRACE a= [1, 0, 1, 0, 1, 1, 0]  new_sets= [[1, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 1, 1, 0]] 

TRACE out_g = [1, 0, 1, 0, 1, 1, 0]
ENTER shiftInPlace, l= [1, 0, 1, 0, 1, 1, 0]
LEAVE shiftInPlace, head= [1]   l= [0, 1, 0, 1, 1, 0, 1]
TRACE a= [0, 1, 0, 1, 1, 0, 1]  new_sets= [[0, 1, 0, 1, 1, 0, 1], [0, 1, 0, 1, 1, 0, 1], [0, 1, 0, 1, 1, 0, 1], [0, 1, 0, 1, 1, 0, 1], [0, 1, 0, 1, 1, 0, 1]] 

TRACE out_g = [0, 1, 0, 1, 1, 0, 1]
ENTER shiftInPlace, l= [0, 1, 0, 1, 1, 0, 1]
LEAVE shiftInPlace, head= [0]   l= [1, 0, 1, 1, 0, 1, 0]
TRACE a= [1, 0, 1, 1, 0, 1, 0]  new_sets= [[1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0]] 

[[1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0]]
Prune
  • 76,765
  • 14
  • 60
  • 81