Студопедия

КАТЕГОРИИ:


Загрузка...

Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Генерация перестановок в лексикографическом порядке

ТЕМА 2. ГЕНЕРАЦИЯ ПЕРЕСТАНОВОК

АЛГОРИТМЫ КОМБИНАТОРИКИ

(лекции 2001 фрагменты)

Санкт-Петербург

 

При решении некоторых задач возникает необходимость генерирования перестановок n-го порядка. Чаще всего генерирование перестановок связано с задачами перебора, в которых решение данной представляет собой некоторую перестановку, обладающую конкретным заданным свойством. Для поиска искомой перестановки мы перебираем все возможные перестановки и проверяем для каждой из них выполнение этого конкретного свойства. Последовательное генерирование перестановок определяет на множестве всех перестановок некоторый порядок, а именно: пусть f и g перестановки, тогда f<g, если в этой генерации перестановка f появляется раньше перестановки g.

Например, предположим, мы разобрали кубик Рубика на отдельные части и собрали его случайным образом. После этого мы хотим проверить, можно ли его преобразовать таким образом, чтобы все его грани были одного цвета. Моделирование подобной задачи на компьютере явно потребует генерации перестановок.

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

Замечание. Интересен вопрос, какого порядка перестановки можно генерировать, в разумное время, на современных ЭВМ? Вследствие того, что общее число перестановок n-го порядка равно n!, современные ЭВМ позволяют генерировать перестановки не более чем 16-го порядка (обоснуйте это!).

Вначале мы рассмотрим алгоритмы генерации всех перестановок в лексикографическом порядке. Этот порядок свойственен расположению слов в различных словарях, поэтому его часто называют словарным. Он характеризуется тем, что буквы алфавита считаются упорядоченным множеством, а слова в словаре располагаются вначале с меньших (ранее перечисленных в алфавите) букв, а затем с больших. Слова, начинающиеся с одинаковых букв, располагаются в зависимости от упорядоченности вторых букв в слове, и так далее. Для перестановок множества {1,2,…,n} числа считаются упорядоченными естественным образом. Формально можно дать следующее определение лексикографического порядка для перестановок.

Определение. Пусть f=<a1,...,an>, g=<b1,...,bn>, будем говорить, что f<g в лексикографическом порядке, если существует k³1 такое, что ak<bk и aq=bq для q<k.

Пример. При n=4 в лексикографическом порядке перестановки располагаются так:



1. <1, 2, 3, 4> 7. <2, 1, 3, 4> 13. <3, 1, 2, 4> 19. <4, 1, 2, 3>
2. <1, 2, 4, 3> 8. <2, 1, 4, 3> 14. <3, 1, 4, 2> 20. <4, 1, 3, 2>
3. <1, 3, 2, 4> 9. <2, 3, 1, 4> 15. <3, 2, 1, 4> 21. <4, 2, 1, 3>
4. <1, 3, 4, 2> 10. <2, 3, 2, 4> 16. <3, 2, 4, 1> 22. <4, 2, 3, 1>
5. <1, 4, 2, 3> 11. <2, 4, 1, 3> 17. <3, 4, 1, 2> 23. <4, 3, 1, 2>
6. <1, 4, 3, 2> 12. <2, 4, 3, 1> 18. <3, 4, 2, 1> 24. <4, 3, 2, 1>

Лексикографический порядок может быть интерпретирован так. Пусть каждая перестановка интерпретируется как целое число, записанное в n-ричной позиционной системе (с цифрами ‘0’«’1’,...,’n-1’«’n’). Тогда генерация их в лексикографическом порядке - это перечисление в порядке возрастания чисел, состоящих из n разных цифр.

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

Л1) В первой перестановке элементы располагаются в возрастающей последовательности, в последней - в убывающей (докажите это свойство для произвольного n).

Л2) Последовательность всех перестановок можно разбить на n блоков длины (n-1)!, соответствующих возрастающим значениям элемента в первой позиции. Остальные n-1 позиций блока, содержащего элемент p в первой позиции, определяют последовательность перестановок множества {1,...,n}/{р} в лексикографическом порядке.

Это свойство легко иллюстрируется приведенным примером генерации перестановок 4-порядка. Нетрудно видеть, что все перестановки 4-порядка разбиты на четыре столбца, при этом у перестановок первого столбца на 1-ой позиции расположен элемент 1, у второго - элемент 2 и так далее. Кроме того, в каждом столбце элементы, расположенные в перестановках со 2-ой по 4-ую позиции, образуют перестановки этих элементов в лексикографическом порядке. Для первого столбца перестановки элементов 2,3,4; для второго - 1,3,4; третьего - 1,2,4; для четвертого 1,2,3. Отметим также, что в каждом столбце элементы, расположенные со 2-ой по 4-ую позиции в первой перестановке, образуют возрастающую последовательность, а в последней перестановке эти же элементы расположены в убывающей последовательности (свойство Л1 лексикографического порядка).

Таким образом, если мы рассмотрим перестановки каждого столбца, то для элементов, расположенных со 2-ой по 4-у позиции, полностью выполняются свойства Л1 и Л2. Это замечание приводит к следующему обобщению свойства Л2 для перестановок произвольного порядка:

Л3) Последовательность всех перестановок можно разбить на n*(n-1)*...*(n-k+1) блоков выбором значений р1,...,pk элементов, расположенных на первых k позициях. При этом блок p1,...,pk предшествует блоку q1,...,qk, если р1,...,pk меньше q1,...,qk в лексикографическом порядке. Кроме того, для перестановок каждого такого обобщенного блока элементы, расположенные с k+1-ой по n-ую позиции, представляют собой генерацию перестановок этих элементов в лексикографическом порядке.

Теперь мы готовы сформулировать самое важное свойство лексикографического порядка, на основе которого легко преобразовать текущую перестановку в следующую. Это свойство можно записать так:

Л4) Любая текущая перестановка является заключительной для некоторого обобщенного блока. Этот блок определяется элементами текущей перестановки, расположенными на позициях в конце перестановки и представляющими собой максимально возможную убывающую последовательность значений элементов перестановки. Справедливость последнего замечания следует из свойства Л1 лексикографического порядка.

В дальнейшем максимально возможную убывающую последовательность значений элементов перестановки, расположенную на позициях в конце перестановки, будем называть “хвостом” перестановки.

Примеры. Рассмотрим приведенную выше генерацию перестановок 4-го порядка, тогда:

Перестановка <2,1,4,3> является заключительной для блока, состоящего из перестановок 7.<2,1,3,4> и 8.<2,1,4,3>, элементы 4,3 образуют ее хвост;

Перестановка <3,1,2,4> является заключительной для блока, состоящего из одной перестановки 13.<3,1,2,4>, ее хвост состоит из одного элемента - 4;

Перестановка <2,4,3,1> является заключительной для второго столбца приведенной генерации, ее хвост - 4,3,1;

Перестановка <4,3,2,1> является заключительной для всей генерации перестановок 4-го порядка, ее хвост совпадает со всей перестановкой.

Как же воспользоваться этим свойством, чтобы преобразовать текущую перестановку в следующую. Это можно сделать по следующему алгоритму:

1. Выделяем хвост текущей перестановки;

2. Если он не совпадает со всей перестановкой, то ищем в хвосте первый с конца перестановки элемент, больший элемента перестановки, расположенного непосредственно перед ее хвостом (если перестановка совпадает со своим хвостом, то она является заключительной во всей генерации);

3. Меняем местами элемент, найденный в предыдущем пункте, с элементом, расположенным непосредственно перед хвостом перестановки;

4. Располагаем все элементы, преобразованного в пункте 3 хвоста перестановки, в обратном порядке (инвертирование преобразованного хвоста перестановки).

Примеры. Перестановка <2,1,4,3> преобразуется по вышеприведенному алгоритму в перестановку <2,3,1,4>, а перестановка <3,1,2,4> в <3,1,4,2>. Рассмотрим перестановку 15-порядка <15,2,4,3,1,13,7,10,14,12,11,9,8,6,5>, она преобразуется в перестановку <15,2,4,3,1,13,7,11,5,6,8,9,10,12,14>.

Упражнение. В какие перестановки преобразуются следующие перестановки: а) n=3, <2,3,1>; б) n=5, <2,5,4,3,1>;

в) n=7, <4,5,2,3,1,6,7>; г) n=8, <2,4,3,6,8,7,5,1>.

Замечание 1. Можно провести формальное доказательство того факта, что преобразованная по данному алгоритму перестановка действительно совпадает со следующей после текущей перестановки в лексикографическом порядке. Однако мы такое доказательство опустим.

Замечание 2. Приведенный выше алгоритм преобразования текущей перестановки в следующую формально можно записать так:

Пусть p=<p1,...,pk,...,pj,...,pn>,где

1£k<n pk<pk+1 и для q:k<q<n следует pq>pq+1

(если p=<n,n-1,...,1>, то k=0),

j>k и pj>pk и для q:j<q£n следует pq<pk;

тогда следующая за p перестановка, при k¹0, имеет вид

<p1,...,pk-1,pj,pn,pn-1,...,pj+1,pk,pj-1,...,pk+1>.

Теперь мы легко можем написать на языке Паскаль алгоритм генерации всех перестановок в лексикографическом порядке. Он основан на поиске k и j в текущей перестановке, транспозиции элементов pk и pj, и инвертировании ее‘хвоста’:

program LEX;

const n=...; {порядок перестановок}

var р : array [0..n] of 0..n; { текущая перестановка}

k : 0..n; j,r,m : 1..n;

<== предыдущая лекция | следующая лекция ==>
| Генерация перестановок в лексикографическом порядке

Дата добавления: 2014-01-04; Просмотров: 545; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.156.54.104
Генерация страницы за: 0.007 сек.