Курсовой проект «Комбинаторные алгоритмы. Поиск кратчайшего пути на графе.»


Генерация перестановок из n элементов



Download 4,55 Mb.
bet4/8
Sana13.02.2023
Hajmi4,55 Mb.
#910548
TuriКурсовой проект
1   2   3   4   5   6   7   8
Bog'liq
Комбинаторные алгоритмы. Поиск кратчайшего пути на графе

Генерация перестановок из n элементов



Постановка задачи


Дано число n, n > 1. Получить все перестановки элементов множества {1, 2, ..., n}.


Перестановка— это упорядоченный набор чисел 1, 2, ..., n , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки.
Перестановка - это упорядоченный набор элементов. Это означает, что порядок элементов в наборе имеет значение. И две перестановки, состоящие из одних элементов, расположенных в разном порядке различными.


Методы решения и описание алгоритмов


Количество различных перестановок множества, состоящего из n элементов равно n!. В этом нетрудно убедиться: на первом месте в перестановке может стоять любой из n элементов множества, после того, как мы на первом месте зафиксировали какой-либо элемент, на втором месте может стоять любой из n – 1 оставшегося элемента и т.д. Таким образом, общее количество вариантов равно n(n – 1)(n – 2)...3*2*1 = n!


итеративный рекурсивный программный граф

Генерация всех перестановок по индексам


Алгоритм заключается в поиске n-факториального представления числа i и восстановлению перестановки по найденному представлению. Мы не будем рассматривать его подробно, так как время работы данного алгоритма есть O(nn!), что не является оптимальным, как в случае следующих алгоритмов.


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

  1. Если множество перестановок P упорядочено антилексикографически, то начальная и конечная перестановки - это соответственно (1, 2, …, n) и (n, n-1,…,1).

  2. Упорядоченная антилексикографически последовательность перестановок по значению последнего элемента в них может быть разбита на n блоков длины (n-1)!. При этом q-й блок на последнем месте имеет элемент, равный (n-q+1), а первые n-1 позиций этого блока определяют последовательность перестановок множества {1,2,…,n}\{q} в антилексикографическом порядке.

Алгоритм генерации перестановок в лексикографическом порядке:
При генерации перестановок в лексикографическом порядке, начиная с тождественной перестановки (1,2,..,n), требуется переходить от уже построенное перестановки a=(a1,…an) к непосредственно следующей за ней перестановкой b=(b1,..bn) до тех пор, пока не получим наибольшую перестановку (n,n-1…,1)(относительно лексикографического порядка).
Рассмотрим способ построения такой перестановки b.Просматриваем справа налево перестановку a=(a1,…an) в поисках самой правой позиции i такой, что aii+1.Если такой позиции нет, то a1>a2>...>an,т.е. a=(n,n-1,…,1) и генерировать больше нечего. Поэтому считаем, что такая позиция i есть. Значит , aii+1>ai+2>…>an. Далее ищем первую позицию j при переходе от позиции n к позиции i такую, что aij. Тогда ii и aj, а в полученной перестановке a,=(a`1,…,a`n)отрезок a`1,…,a`n-1, a`n переворачиваем. Построенную перестановку обозначим через b. Например, пусть a=(2,6,5,8,7,4,3,1). Тогда ai=5 и aj=7. Поменяем местами эти элементы, повернем отрезок (8,5,4,3,1) и получим перестановку b=(2,6,7,1,3,4,5,8).
Сложность такого алгоритма - O(n!).
Программа, демонстрирующая генерации перестановок в лексикографическом порядке представлена в приложении.



Download 4,55 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish