Clever Geek Handbook

Is this an efficient way to generate Thue-Morse sequence in Python?

Is using a generator like the code below an efficient way to generate Thue-Morse sequence in Python?

# generate the Thue-Morse sequence
def genThueMorse():
    # initialize
    tms = '0'
    curr = 0
    while True:
        # generate next sequence
        if curr == len(tms):
            tmp = ''
            for i in range(len(tms)):
                if tms[i] is '0':
                    tmp += '1'
                else:
                    tmp += '0'
            tms += tmp
        yield tms[curr]
        curr +=1

Here's the code to check:

tms = koch.genThueMorse()
while True:
   print(next(tms))
0


source to share


3 answers


It's short, is it effective?



import itertools

def genThueMorse():
    for n in itertools.count():
        yield (1 if bin(n).count('1')%2 else 0)
+2


source


I think the generator will be quite efficient. I would go for something like this:



from itertools import count, izip

def genThueMorse():
    tms = [0]
    invert = [1, 0]
    for tm, curr in izip(tms, count()):
        yield str(tm)
        if curr == len(tms) - 1:
            tms += [invert[c] for c in tms]
+1


source


Helping to complement the other answers: If you only want to compute the nth digit in a sequence, use:

lambda n: bin(n).count("1") % 2

or, if you prefer a function:

def calculate_nth(n):
  return bin(n).count("1") % 2

Example:

f = lambda n:  bin(n).count("1") % 2
f(0) # This will return 0
f(1) # This will return 1
f(2) # This will return 1
...
f(10) # This will return 0

This can be checked using the sequence: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

+1


source






More articles:


All Articles