0

Is using a generator as in the code below, an efficient way to generate the 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 is code to test it:

tms = koch.genThueMorse()
while True:
   print(next(tms))
M-V
  • 5,167
  • 7
  • 52
  • 55

3 Answers3

3

This is concise, is it "efficient"?

import itertools

def genThueMorse():
    for n in itertools.count():
        yield (1 if bin(n).count('1')%2 else 0)
mhawke
  • 84,695
  • 9
  • 117
  • 138
  • This is exactly the right idea; a closed-form representation avoids the need to store the entire sequence-so-far within the generator (which makes the generator itself look silly). As for how to actually count the bits, see also: http://stackoverflow.com/questions/9829578/fast-way-of-counting-bits-in-python – Karl Knechtel Aug 05 '14 at 05:17
  • Nice. No extra memory used. Then the problem moves into fast ways of counting bits. https://stackoverflow.com/questions/9829578/fast-way-of-counting-bits-in-python – hughdbrown Aug 05 '14 at 05:23
  • Re: `yield (1 if bin(n).count('1')%2 else 0)` -- since `bin(n).count('1') % 2` is 1 when you return 1 and 0 when you return 0, you should be able to write the code like this: `yield bin(n).count('1') % 2`. Maybe your way is more explicit about returning 1 or 0. – hughdbrown Dec 11 '15 at 22:28
  • @hughdbrown: good point. I don't remember what I was thinking back then, so I can't claim that I purposely wrote it that way to be more explicit, although it is. There is certainly an efficiency gain in removing the `if/else` .. – mhawke Dec 12 '15 at 00:37
1

I think a generator will be fairly 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]
hughdbrown
  • 47,733
  • 20
  • 85
  • 108
1

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

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

or if 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 verified with the sequence: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

agmezr
  • 350
  • 2
  • 15