Последовательность морса туэ python

Задача №1 на последовательность ТуЭ-Морса

Найти последовательность из 50 нулей и единиц, в которой никакой отрезок не повторяется три раза подряд или установить,что такой последовательности не существует.

Решение:

Воспользуемся уже придуманной последовательностью Туэ-Морса (вики).

История:

Публикация работы Туэ в Германии прошла бесследно, и последовательность вновь открывает Марсон Морс (Marston Morse) в 1921 году, применив её в дифференциальной геометрии.

Последовательность открывалась независимо много раз: например гроссмейстер Макс Эйве открыл её применение в шахматах, показав, как играть бесконечно, не нарушая правил ничьи.

Для нашей задачи нужно, чтобы никакой отрезок в последовательности не повторялся 3 раза подряд, как написано ниже, последовательность Туэ-Морса подходит для этого:

Свойства:

• симметрия;
• в последовательности никогда не встречаются три одинаковых подряд идущих куска, то есть невозможно встретить AAA, где под A можно подразумевать любую конечную последовательностей нулей и единиц;
• фурье-преобразование последовательности имеет одинаковые максимумы на частотах 1/3 и 2/3.
• число, двоичной записью которого является последовательность Морса-Туэ, называется числом Пруэ-Туэ-Морса.

Алгоритм:

Программирование:

Для решения задачи будем использовать тип string. Сначала напишем функцию для инвертирования строки, т.е. в строке меняем 1 на 0, 0 на 1:

Источник

Является ли это эффективным способом создания последовательности Туэ-Морса в Python?

Использует генератор, как в приведенном ниже коде, это эффективный способ создания Thue-Morse последовательность в 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 

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

Ответы (3)

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

Это совершенно правильная идея; представление в закрытой форме избавляет от необходимости хранить всю последовательность внутри генератора (что делает сам генератор глупым). Что касается фактического подсчета битов, см. Также: stackoverflow.com/questions/9829578/ — person Karl Knechtel; 05.08.2014

Отлично. Никакой дополнительной памяти не используется. Затем проблема переходит в быстрые способы подсчета битов. stackoverflow.com/questions/9829578 / — person hughdbrown; 05.08.2014

Re: yield (1 if bin(n).count(‘1’)%2 else 0) — поскольку bin(n).count(‘1’) % 2 равно 1, когда вы возвращаете 1, и 0, когда вы возвращаете 0, вы можете написать такой код: yield bin(n).count(‘1’) % 2 . Возможно, ваш способ более ясен в отношении возврата 1 или 0. — person hughdbrown; 12.12.2015

@hughdbrown: хороший момент. Я не помню, о чем я думал тогда, поэтому я не могу утверждать, что я специально написал это таким образом, чтобы быть более ясным, хотя это так. Безусловно, эффективность удаления if/else .. — person mhawke; 12.12.2015

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] 

Почему бы не изменить counter = count(); while True: curr = counter.next() на for curr in count(): ? — person icktoofay; 05.08.2014

@icktoofay: хорошая идея. Я изначально думал, что такой цикл остановится на 0. — person hughdbrown; 05.08.2014

Помогает дополнить другие ответы: если вы хотите вычислить только n-ю цифру в последовательности, используйте: lambda n: bin(n).count(«1») % 2 или, если предпочитаете функцию:

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

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 

Источник

Это эффективный способ генерации последовательности Туэ-Морса в Python?

Является ли использование генератора, как в коде ниже, эффективным способом генерации последовательности Туэ-Морса в 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 

Вот код, чтобы проверить это:

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

3 ответа

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

Я думаю, что генератор будет довольно эффективным. Я бы пошел на что-то вроде этого:

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] 

Помощь в дополнении других ответов: Если вы хотите только вычислить n-ую цифру в последовательности, используйте:

или если предпочитаете функцию:

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

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 

Это можно проверить с помощью последовательности: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

Источник

Запишите последовательность Туэ-Морса

На этом сайте довольно много задач, которые просят вас распечатать последовательность, и это не исключение.

(Следующее объяснение последовательности для этого вызова предполагает, что символы в последовательности являются 0 и 1 .)

Рекурсивное определение последовательности Туэ-Морса таково , что

T_0 = 0 T_2n = T_n T_2n+1 = 1 - T_n 

Более прямое определение является то , что последовательность из , 0 чтобы 2**m-1 и 2**m to 2**(m+1)-1 бинарные комплементы. Так 0 следует 1 , 01 следует 10 , 0110 следует 1001 , и, пропустив вперед немного, 0110100110010110 следует 1001011001101001 .

Задача состоит в том, чтобы написать программу или функцию, которая печатает последовательность Туэ-Морса для первых n элементов, где n любое неотрицательное целое число. Выходные данные могут использовать любые два символа, как показано в примерах ниже.

>>> tm_01(20) 01101001100101101001 >>> tm_ab(42) abbabaabbaababbabaababbaabbabaabbaababbaab >>> tm_paren(37) ())()(())(()())()(()())(())()(())(()( >>> tm_space_star(12) ** * ** * >>> tm_01(0) # to show that this is a valid input 

• На входе будет любое неотрицательное целое число. Вы можете предположить, что все входные данные действительны.
• Выходными данными должны быть первые n элементы последовательности Туэ-Морса с использованием любых удобных символов. Если вам нравится, вы также можете добавить разделитель. В моих примерах у меня нет. Примечание. Это правило разрешает списки (например, списки Python), так как , это допустимый разделитель, и я не против начальных или конечных символов, таких как [ и ] в выходных данных.
• Это код гольф, поэтому выигрывает наименьшее количество байтов.

Как всегда, если проблема неясна, пожалуйста, дайте мне знать. Удачи и хорошего гольфа!

Каталог

var QUESTION_ID=65549;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index)return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page pun">+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter pun">+ANSWER_FILTER>function commentUrl(index,answers)return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page pun">+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter pun">+COMMENT_FILTER>function getAnswers()jQuery.ajax(url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data)answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a)a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a>);if(!data.has_more)more_answers=false;comment_page=1;getComments()>>)>function getComments()jQuery.ajax(url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data)data.items.forEach(function(c)if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)>);if(data.has_more)getComments();else if(more_answers)getAnswers();else process()>>)>getAnswers();var SCORE_REG=/\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*|[^\n<>]+>)[^\n\d<>]*)*)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a)return a.owner.display_name>function process()var valid=[];answers.forEach(function(a)var body=a.body;a.comments.forEach(function(c)if(OVERRIDE_REG.test(c.body))body='
'+c.body.replace(OVERRIDE_REG,'')+'
'>);var match=body.match(SCORE_REG);if(match)valid.push(user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,>);else console.log(body)>);valid.sort(function(a,b)var aB=a.size,bB=b.size;return aB-bB>);var languages=<>;var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a)if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace(">",lastPlace+".").replace(">",a.user).replace(">",a.language).replace(">",a.size).replace(">",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery(''+lang+'').text();languages[lang]=languages[lang]||lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link>>);var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b)if(a.lang_raw>b.lang_raw)return 1;if(a.lang_rawb.lang_raw)return-1;return 0>);for(var i=0;ilangs.length;++i)var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace(">",lang.lang).replace(">",lang.user).replace(">",lang.size).replace(">",lang.link);language=jQuery(language);jQuery("#languages").append(language)>>

bodytext-align:left!important>#answer-listpadding:10px;width:290px;float:left>#language-listpadding:10px;width:290px;float:left>table theadfont-weight:700>table tdpadding:5px>

 src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js">  rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">  id="language-list"> Shortest Solution by Language   class="language-list">  Language User Score    id="languages">     id="answer-list"> Leaderboard   class="answer-list">  Author Language Size    id="answers">     style="display: none">  id="answer-template">  > > > >  href=">">Link     style="display: none">  id="language-template">  > > >  href=">">Link   

Источник