Словари со смешанными значениями

Словари могут состоять не только из строк. Значения словарей могут быть любого типа, включая целые, логические, произвольные объекты, или даже другие словари. И значения в одном словаре не обязаны быть одного и того же типа; можно смешивать и сочетать их, как вам необходимо. Ключи словаря более ограниченны, но они могут быть строками, целыми числами и некоторыми другими типами. Ключи разных типов тоже можно смешивать и сочетать в одном словаре.

ПРИМЕР ХРАНЕНИЯ СПИСКОВ В СЛОВАРЕ

>>> SUFFIXES = {1000: ['KB', 'MB', 'GB', 'TB', 'PB', 'EB', 'ZB', 'YB'], … 1024: ['KiB', 'MiB', 'GiB', 'TiB', 'PiB', 'EiB', 'ZiB', 'YiB']}
>>> len(SUFFIXES) #1
2
>>> 1000 in SUFFIXES #2
True
>>> SUFFIXES[1000] #3
['KB', 'MB', 'GB', 'TB', 'PB', 'EB', 'ZB', 'YB']
>>> SUFFIXES[1024] #4
['KiB', 'MiB', 'GiB', 'TiB', 'PiB', 'EiB', 'ZiB', 'YiB']
>>> SUFFIXES[1000][3] #5
'TB'

1. Так же, как для списков и множеств, функция len() возвращает количество элементов словаря.

2. И так же, как со списками и множествами, можно использовать оператор in, чтобы проверить, определён ли конкретный ключ в словаре.

3. 1000 является ключом в словаре SUFFIXES; его значение — список из восьми элементов (восьми строк, если быть точным).

4. Аналогично, 1024 — ключ словаря SUFFIXES; и его значение также является списком из восьми элементов.

5. Так как SUFFIXES[1000 ] является списком, то можно обратиться к отдельным элементам списка по их порядковым номерам, которые индексируются с нуля.

Пример дешифрации текста после алфавитной замены

Рассмотрим следующую учебную задачу из области защиты информации: раскодировать текст, зашифрованный шифром перестановки, при помощи частотного анализа.
Известно, что перестановкой перепутаны буквы: а, в, е, з, о, п, р, с, т, у, ф, ц, ш, ь.
Остальные буквы текста не тронуты.

ДАН ТЕКСТ:

оншчшль был эеа ьдиный, кзгз о шедш ншсыошли илюошцшезм. зн фзсдшл тьеоых шинае, фоящьнных, быорих тзезждьниями ьгз мыфли, и зни были ф ним сшдзлгз дз фзцозеьния офьгз тезчьгз. эеа гзозеил ф ними, теьдлшгшя им мьлздии; шинае тьли ьма, и зн ешдзошлфя. здншкз дзлгзь оеьмя шинае тьли тзздинзчкь либз о ньфкзлвкз гзлзфзо, ш зфцшлвныь цьм оеьмьньм фларшли; ибз были зни фтзфзбны тзфцичв лирв ца чшфцв сшмыфлш илюошцшеш, к кзцзезма фшми имьли ньтзфеьдфцоьннзь зцнзрьниь. тзнимшниь фзбешцвьо теихздилз к ним тзфцьтьннз, нз тз мьеь фларшния знз езфлз и аоьличиошлз фзглшфиь и гшемзничнзфцв тьния. фзсошл здншжды илюошцше офьх шинае и теьдлзжил им мьлздию оьликзй филы, ешфкеыошораю им цшйны бзльь чадьфныь и сншчимыь, чьм ць, чцз кзгдш-либз теьждь зцкеыошлифв им. кешфзцш ьь ншчшлвных нзц и оьликзльтиь кзнузоки зчшезошлз шинае, и о мзлчшнии фклзнилифв зни тьеьд илюошцшезм. и фкшсшл им цзгдш илюошцше: — ис эцзй мьлздии, чцз я ошм дшл, тзоьльошю флзжицв гшемзничнзь соачшниь оьликзй масыки. и тзьлика сшжьг я о кшждзм ис ошф ньагшфимзь тлшмя, оы тзоинны теилзжицв офь фози афилия к фзоьерьнфцозошнию фьй мьлздии, и озлвны бадьць олзжицв о ньь, теи жьлшнии, фози фзбфцоьнныь мыфли и чшяния. я жь бада фидьцв и фларшцв, ншфлшждшяфв цьм, кшк ошрш оьликшя кешфзцш ислиошьцфя о тьфню. и сшсоачшли гзлзфш шинае, тздзбныь соакшм шеп и люцньй, фоиеьльй и цеаб, оизл и зегшнш, и мнзгзгзлзфзма тзющьма хзеа, и теинялифв флшгшцв мьлздию илюошцшеш о оьличшйраю масыка. бьфкзньчнз исмьнчиоыь мьлздии фцшли фтльцшцвфя о гшемзничнзь фзсоачиь, оыхздиорьь нш оыфзчшйрих и нисрих нзцшх сш гешни флыримзфци, и мьфцз збицшния илюошцшеш тьеьтзлнилзфв соакзм. масыкш эцш и эхз ьь дзфцигли оньрньй тафцзцы, и цш тьеьфцшлш быцв тафцзцзй.

 

При помощи написанной выше функции ChastotnyAnaliz получаем количества символов в тексте, отсортированные по убыванию, и сличаю их с частотами символов произвольного текста-образца из Интернета на русском языке (например, первые 5 строф 1 главы Евгения Онегина):

Частоты символов:	частоты в тексте-образце:
и — 153	о — 144
з — 143	е — 125
ш — 115	н — 109
ь — 113	а — 105
л — 90	и — 92
н — 86	л — 78
ф — 76	с — 69
о — 72	т — 65
ц — 58	д — 59
е — 55	в — 58
м — 52	м — 58
а — 39	р — 55
д — 36	у — 51
т — 36	г — 43
ы — 35	ь — 40
к — 32	к — 38
ч — 25	п — 36
г — 24	я — 30
с — 23	б — 29
в — 22	ы — 24
я — 21	з — 23
б — 18	ч — 23
ю — 16	й — 21
р — 15	ж — 20
ж — 12	х — 16
й — 12	ш — 12
х — 12	ц — 6
э — 5	ю — 6
щ — 2	ф — 2
п — 1	ъ — 1
у — 1	э — 1
ъ — 0	щ — 0

В таблице отметим символы, для которых частоты встречи в расшифровываемом тексте разительно отличаются от частот таковых в нормальном русском тексте.
Сличая таблицы, приходим к выводу, что нужно осуществить следующие замены: з → о, ш → е, ь → а, ф → с, о → т, ц → в, е → р, а → у, т → ь, с → п, в → з, р → ш, п → ц, у → ф.

Осуществляем эти замены в любом текстовом редакторе в следующем порядке:

1. предварительно заменим все исходные буквы «о» на «@», чтобы они потом не перепутались c результатом замены буквы «з»

2. з на о — заменить все

3. в на з — заменить все

4. ц на в — заменить все

5. п на ц — заменить все

6. с на п — заменить все

7. ф на с — заменить все

8. у на ф — заменить все

9. а на у — заменить все

10. ь на а — заменить все

11. т на ь — заменить все

12. @ на т — заменить все

ИТОГ ВСЕХ ЗАМЕН:

тншчшла был эеу адиный, кого т шедш ншпытшли илютшвшеом. он сопдшл ьаетых шинуе, стящанных, бытрих ьоеожданиями аго мысли, и они были с ним пшдолго до совтоеания тсаго ьеочаго. эеу готоеил с ними, ьеадлшгшя им малодии; шинуе ьали аму, и он ешдотшлся. одншко долгоа теамя шинуе ьали ьоодиночка либо т насколзко голосот, ш освшлзныа вам теаманам слуршли; ибо были они сьособны ьосвичз лирз ву чшсвз пшмыслш илютшвшеш, к ковоеому сшми имали наьосеадсвтанноа овнораниа. ьонимшниа собешвзат ьеиходило к ним ьосваьанно, но ьо маеа слуршния оно еосло и уталичитшло соглшсиа и гшемоничносвз ьания. соптшл одншжды илютшвше тсах шинуе и ьеадложил им малодию таликой силы, ешскеытштрую им вшйны болаа чудасныа и пншчимыа, чам ва, чво когдш-либо ьеажда овкеытшлисз им. кешсовш аа ншчшлзных нов и таликолаьиа конфотки очшеотшло шинуе, и т молчшнии склонилисз они ьаеад илютшвшеом. и скшпшл им вогдш илютшвше: — ип эвой малодии, чво я тшм дшл, ьоталатшю сложивз гшемоничноа птучшниа таликой мупыки. и ьоалику пшжаг я т кшждом ип тшс наугшсимоа ьлшмя, ты ьотинны ьеиложивз тса стои усилия к сотаерансвтотшнию сай малодии, и толзны будава тложивз т наа, ьеи жалшнии, стои собсвтанныа мысли и чшяния. я жа буду сидавз и слуршвз, ншслшждшясз вам, кшк тшрш таликшя кешсовш иплитшався т ьасню. и пшптучшли голосш шинуе, ьодобныа птукшм шец и лювнай, стиеалай и веуб, тиол и оегшнш, и многоголосому ьоющаму хоеу, и ьеинялисз слшгшвз малодию илютшвшеш т таличшйрую мупыку. басконачно ипманчитыа малодии свшли сьлавшвзся т гшемоничноа соптучиа, тыходитраа нш тысочшйрих и ниприх новшх пш гешни слыримосви, и масво обившния илютшвшеш ьаеаьолнилосз птуком. мупыкш эвш и эхо аа досвигли тнарнай ьусвовы, и вш ьаеасвшлш бывз ьусвовой.

 

При взгляде на текст, очевидно, что в некоторых заменах мы не попали в необходимые символы. Напрашиваются замены:

1) т на в
2) в на т
3) временно заменяем е собачкой @
3) а на е
4) ш на а
5) после этого очевидно, что @ — это буква р, но перед заменой нужно заменить р на #
6) @ на р
7) очевидно, что # — это ш, но перед этим ш на %
8) # на ш

ИТОГ ВСЕХ ЗАМЕН:

вначале был эру единый, кого в арда напывали илюватаром. он сопдал ьервых аинур, священных, бывших ьорождениями его мысли, и они были с ним падолго до сотворения всего ьрочего. эру говорил с ними, ьредлагая им мелодии; аинур ьели ему, и он радовался. однако долгое время аинур ьели ьоодиночке либо в несколзко голосов, а осталзные тем временем слушали; ибо были они сьособны ьостичз лишз ту частз памысла илюватара, к которому сами имели неьосредственное отношение. ьонимание собратзев ьриходило к ним ьостеьенно, но ьо мере слушания оно росло и увеличивало согласие и гармоничностз ьения. сопвал однажды илюватар всех аинур и ьредложил им мелодию великой силы, раскрывавшую им тайны более чудесные и пначимые, чем те, что когда-либо ьрежде открывалисз им. красота ее началзных нот и великолеьие конфовки очаровало аинур, и в молчании склонилисз они ьеред илюватаром. и скапал им тогда илюватар: — ип этой мелодии, что я вам дал, ьовелеваю сложитз гармоничное пвучание великой мупыки. и ьоелику пажег я в каждом ип вас неугасимое ьламя, вы ьовинны ьриложитз все свои усилия к совершенствованию сей мелодии, и волзны будете вложитз в нее, ьри желании, свои собственные мысли и чаяния. я же буду сидетз и слушатз, наслаждаясз тем, как ваша великая красота ипливается в ьесню. и папвучали голоса аинур, ьодобные пвукам арц и лютней, свирелей и труб, виол и органа, и многоголосому ьоющему хору, и ьринялисз слагатз мелодию илюватара в величайшую мупыку. бесконечно ипменчивые мелодии стали сьлетатзся в гармоничное сопвучие, выходившее на высочайших и нипших нотах па грани слышимости, и место обитания илюватара ьереьолнилосз пвуком. мупыка эта и эхо ее достигли внешней ьустоты, и та ьерестала бытз ьустотой.

 

Видно, что:

1. п на з

2. ь на п

3. з на ь

УРА!!!

ОКОНЧАТЕЛЬНЫЙ ВАРИАНТ:

вначале был эру единый, кого в арда называли илюватаром. он создал первых аинур, священных, бывших порождениями его мысли, и они были с ним задолго до сотворения всего прочего. эру говорил с ними, предлагая им мелодии; аинур пели ему, и он радовался. однако долгое время аинур пели поодиночке либо в несколько голосов, а остальные тем временем слушали; ибо были они способны постичь лишь ту часть замысла илюватара, к которому сами имели непосредственное отношение. понимание собратьев приходило к ним постепенно, но по мере слушания оно росло и увеличивало согласие и гармоничность пения. созвал однажды илюватар всех аинур и предложил им мелодию великой силы, раскрывавшую им тайны более чудесные и значимые, чем те, что когда-либо прежде открывались им. красота ее начальных нот и великолепие конфовки очаровало аинур, и в молчании склонились они перед илюватаром. и сказал им тогда илюватар: — из этой мелодии, что я вам дал, повелеваю сложить гармоничное звучание великой музыки. и поелику зажег я в каждом из вас неугасимое пламя, вы повинны приложить все свои усилия к совершенствованию сей мелодии, и вольны будете вложить в нее, при желании, свои собственные мысли и чаяния. я же буду сидеть и слушать, наслаждаясь тем, как ваша великая красота изливается в песню. и зазвучали голоса аинур, подобные звукам арц и лютней, свирелей и труб, виол и органа, и многоголосому поющему хору, и принялись слагать мелодию илюватара в величайшую музыку. бесконечно изменчивые мелодии стали сплетаться в гармоничное созвучие, выходившее на высочайших и низших нотах за грани слышимости, и место обитания илюватара переполнилось звуком. музыка эта и эхо ее достигли внешней пустоты, и та перестала быть пустотой.

 

Теперь можно опознать, что этот текст взят из первой главы книги «Сильмариллион» Дж.Р.Р.Толкиена.

Рекурсивный перебор

Важную роль среди алгоритмов играют алгоритмы перебора различных комбинаторных структур. Например, можно перебирать все подмножества данного множества, все подмножества, содержащие заданное число элементов, все перестановки данного набора элементов. Основным способом перебора комбинаторных структур является рекурсия.

ПЕРЕБОР ВСЕХ ПОДМНОЖЕСТВ

Пусть дано некоторое множество, содержащее n элементов a0, a1, …, an−1. Необходимо перебрать все его подмножества. Общее число подмножеств n-элементного множества равно 2n. Например, у множества из 3 элементов {1,2,3} восемь подмножеств: {} (пустое подмножество), {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.

Каждое подмножество будем кодировать строкой из n символов, где i-й символ будет равен 0, если aiне входит в выбранное подмножество, или равен 1, если ai входит в выбранное подмножество. То есть строка из одних нулей соответствует пустому множеству, а строка из одних единиц соответствует подмножеству, совпадающему со всем множеством.

Таким образом, задача сводится к перебору всех двоичных строк (т. е. состоящих из символов 0 или 1) длины n. Строки будем перебирать в лексикографическом порядке, то есть для n=3 порядок будет таким:

000
001
010
011
100
101
110
111

В лексикографическом порядке все строки упорядочены по первому символу, т. е. сначала нужно вывести те строки, у которых первый символ равен 0, затем те строки, у которых первый символ равен 1. Те строки, у которых первые символы равны, упорядочены по второму символу, затем - по третьему и т. д.

Если посмотреть на пример для n=3 то можно видеть, что результат перебора построен по следующему принципу. Сначала нужно взять первый символ строки равный 0, затем к нему всеми возможными способами дописать следующие n−1 символ также в лексикографическом порядке. Потом поставим на первое место символ, равный 1 и допишем к нему всеми возможными способами следующие n−1 символ.

В свою очередь, если у нас уже есть какая-то сформированная начальная часть строки (например, первый символ равен 0), то нужно к нему добавить сначала символ 0 (получим начальную часть вида 00) и так же рекурсивно дописать оставшиеся n−2 символа, затем добавить символ 1 (получим начальную часть вида 01), и рекурсивно добавить к этой начальной части еще n−2 символа.

Решение оформим в виде рекурсивной функции generate с двумя параметрами. Первый параметр — число n равное количеству символов строки, которые нужно сгенерировать. Второй параметр — строка prefix, в которой хранится уже сгенерированная начальная часть строки. Функция будет добавлять по одному символу к уже построенной части prefix, сначала добавляя символ «0», затем символ «1», после чего функция будет рекурсивно вызывать себя для построения n−1 оставшегося символа.

Окончание рекурсии: случай n=0, в этом случае функция больше не должна ничего строить и должна вывести построенную строку, которая целиком будет храниться в переменной prefix. Если требуется не вывести полученные строки на экран, а как-то обработать данное подмножество, то вместо функции print нужно вызвать функцию обработки подмножества.

Во всех остальных случаях функция дважды вызывает себя рекурсивно для построения строки длины n−1 - сначала добавив к строке prefix «0», затем добавив «1». Функция может быть реализована следующим образом:

def generate(n, prefix):
if n == 0:
print(prefix)
else:
generate(n - 1, prefix + "0")
generate(n - 1, prefix + "1")

Для того, чтобы вывести все двоичные строки длины 5, нужно вызвать эту функцию так:

generate(5, "")

Попробуем модифицировать эту функцию. Допустим, нужно вывести все двоичные строки, в которых нет двух символов «1» подряд. Это означает, что добавить символ «1» можно только в том случае, если prefix оканчивается на символ «0», а также в случае пустой строки. Нужно добавить только одно условие:

def generate(n, prefix):
if n == 0:
print(prefix)
else:
generate(n - 1, prefix + "0")
if prefix == "" or prefix[-1] == "0":
generate(n - 1, prefix + "1")