Is This An Efficient Way To Generate The Thue-morse Sequence In Python?
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
Solution 1:
This is concise, is it "efficient"?
import itertools
defgenThueMorse():
for n in itertools.count():
yield (1ifbin(n).count('1')%2else0)
Solution 2:
I think a generator will be fairly efficient. I would go for something like this:
from itertools import count, izip
defgenThueMorse():
tms = [0]
invert = [1, 0]
for tm, curr in izip(tms, count()):
yieldstr(tm)
if curr == len(tms) - 1:
tms += [invert[c] for c in tms]
Solution 3:
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:
defcalculate_nth(n):
returnbin(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: 011 0 1 0 0 1 1 0 0 1 0 1 1 0
Post a Comment for "Is This An Efficient Way To Generate The Thue-morse Sequence In Python?"