Раздел: Документация
0 ... 64 65 66 67 68 69 70 ... 117 дется перемножать перестановки (т. е. выполнять их одну за другой). Мы будем использовать обозначения сравнений по модулю: а = Ь mod m, где а, Ь, т суть целые числа и т ф 0, означает, что а - Ь = Am для некоторого целого Л, которое может быть > 0, < 0 или нулем. Изучается порядок перестановки, полученной тасованием колоды карт, который означает, сколько раз надо выполнить заданное ею тасование, чтобы вернуть картам их исходный порядок. (К несчастью, здесь возникает терминологическое недоразумение между «порядком» перестановки и «порядком» в перестановке! В последнем случае имеется в виду положение карт в колоде.) Используется разложение перестановок на непересекающиеся циклы. Замечание: Мы всегда записываем композицию перестановок справа налево: запись тггтг! означает «выполни сначала тгх, а затем выполни 7Г2 ». Используемые возможности MATLABa Придется делать некоторые изменения в имеющихся М-файлах, например, чтобы использовать вместо нечетных номеров четные. Нам понадобится команда MATLABa sort. 14.1. Введение Ц.1.1. Перестановки мест (ПМ) Рассмотрим стопку из шести карт, пронумерованных сверху вниз числами 1, 2, 3, 4, 5, 6. Предположим, что их переупорядочили (перетасовали) так, что порядок значений стал 4, 1, 5, 2, 6, 3 сверху вниз. Соответствующая перестановка мест (ПМ) есть /1 23 4 5 6 \ Ж~2 4 6 1 35,/ где тг(х) = у (она задается верхней строкой х и записанной прямо под ней - элемент под элементом - нижней строкой у) означает, что карта, первоначально находившаяся в колоде сверху на месте х, перемещается на место у (тоже сверху). Большинство тасований лучше всего описывается с помощью соответствующих им ПМ. Так, например, приведенное в начале есть «тасование внахлест», когда карты сначала делятся на две равные стопки со значениями 4, 5, 6 сверху вниз и 1, 2, 3 сверху вниз. Эти стопки снова объединяются, перемежаясь. Повторяя то оке самое тасование внахлест, снова получаем сначала две стопки со значениями 2, 6, 3 и 4, 1, 5, а затем объединенную стопку со значениями 2, 4, 6, 1, 3, 5 сверху вниз. Вы можете проверить для себя, что ПМ, соответствующее этому двойному тасованию, есть просто квадрат тг (выполняем тг и затем опять выполняем тг): а / 1 2 3 4 5 6 Л \ 4 1 5 2 6 3 У Мы можем теперь «снять сверху»: разделить колоду на две стопки 2, 4, 6 и 1, 3, 5 и снова объединить так, чтобы получить порядок значений 1, 3, 5, 2, 4, 6. Вся последовательность трех тасований (два внахлест и снятие) имеет, следовательно, ПМ / 1 2 3 4 5 6 N \ 1 4 2 5 3 6 j Заметьте, что снятие само по себе имеет ПМ /123 4 5 6 ° ~ \ 4 5 6 1 2 3 (карта с места 1 переходит на место 4 и т.д.). Вы можете легко проверить, что перестановка из (14.2) есть в точности С7г2. Таким образом, можно очень наглядно представить ПМ результата трех тасований, перемножая их ПМ справа налево, что записывается Как (77Г2. Пусть в общем случае мы сделали несколько тасований с ПМ 7Ti; затем 7Г2 и т. д. до тгг. Тогда ПМ суммарного тасования есть произведение перестановок TrTirr-i . .. tti . В частности, повторение тасования с ПМ = тг общим числом г раз подряд эквивалентно тасованию с ПМ =тгг. Чтобы в дальнейшем писать покороче, мы будем описывать ПМ только их нижней строкой. Верхняя строка всегда имеет вид 1,2,... , п. Иногда (§ 14.3) нас будет интересовать разложение ПМ на непересекающиеся циклы. Конечно, обычные игральные карты имеют масть. Мы же вместо этого будем маркировать их значениями 1,2,... ,52. Это равносильно упорядочиванию мастей и упорядочиванию А,2,... , 10,J,Q,K (туз, 2, ..., 10, валет, дама, король) карт одной масти. 14-1-2. Использование команды MATLABasort В MATLABe есть способ автоматического перехода от перестановок места (ПМ) к указанным на картах значениям, а именно команда sort. Предположим, что мы начинаем с шести карт в естественном порядке 1, 2, 3, 4, 5, 6. Выполните следующее в MATLABe » р= [2 6 4 1 5 3] ; Или любой другой список: это ПМ » [v q]=sort (р) ; » q Вы обнаружите, что вектор ддает значения карт слева направо (которые мы понимаем как значения сверху вниз в колоде). Заметьте, что v здесь не используется, но он необходим, поскольку является частью команды sort1). И наоборот, если рассматривать q как перестановку мест, то р есть вектор значений карт слева направо, так что этот прием работает в обе стороны. Итак, решающее преимущество метода ПМ состоит в том, что перемножением ПМ двух тасований обычным образом мы получаем ПМ объединенного тасования карт. Мы всегда можем перейти к упорядочиванию по значениям, используя sort, и это сделано для вас в М-файлах. 14.2. Тасования внутрь и поверх2 Возьмите колоду из п карт, промаркированных как 1,2,... ,п, и разделите ее на две части, по возможности равные. Идеальное тасование внахлест получается перемежающимся слиянием этих двух половинок колоды. Имеется четыре возможности в соответствии с тем, четно или нечетно и, и с тем, из какой части выбирается первая карта. 14-2.1. Четные тасования внутрь Если п четно, т.е. п = 2А;, то две половинки колоды состоят из карт 1,2,... ,кик + 1,к+2,... , 2к. Если карта к + 1 идет наверх первой, то это называется тасованием внутрь, и карты по значениям расположатся так: fc + 1,1, к + 2,2, к + 3,3,..., 2к, к. На рис. 14.1 приведен случай к = 3. Выпишите соответствующую перестановку мест, скажем, тг, и проверьте (хотя бы на двух примерах, таких, как п = 6, п = 10), В V- sort(p) здесь будет получаться v = [1,2,... . п].Еслир- перестановка из чисел 1,2,... , п, то обратная ей перестановка q может быть вычислена непосредственно из ее определения как q(p) - 1 : п.Этот способ работает быстрее, чем команда sort. -Прим. перев. 2 В оригинале: ins and out-shuffle. Мы перевели это как «тасование внутрь и поверх». - Прим. перев. 0 ... 64 65 66 67 68 69 70 ... 117
|
