Алгоритм 1.

Розглянемо деяку перестановку з натуральних чисел 13 5 4 2

Знайдемо першу з кінця перестановки впорядковану пару (3 5). Перше число називають числом, що обриває. Хвіст перестановкиутворює послідовність чисел, яка починається з числа, що обриває.

Підалгоритм ревпорядкування хвоста перестановки.

1. замінити число, що обриває, на найменше з хвоста перестановки, яке більше його.

2. всі інші числа з хвоста перестановки разом з тим, що обриває розташивати впорядку зростання:

1 3 5 4 2 число, яке обриває - 3.

3 5 4 2 хвіст перестановки

Робота буде закінчена, коли всі числа будуть розташовані в порядку спадання.

Таблиця 4.1. Таблиця трасування створення перестановок

№ перестановки	перестановк а	число, що обриває	хвіст перестановки	ревпорядкува ння хвоста перестановки
	1 2 3 4		3 4	4 3
	1 2 4 3		2 4 3	3 2 4
	1 3 2 4		2 4	4 2
	1 3 4 2		3 4 2	4 2 3
	1 4 2 3		2 3	3 2
	1 4 3 2		1 4 3 2	2 1 3 4
	2 1 3 4		3 4	4 3
	2 1 4 3		1 4 3	3 1 4
	2 3 1 4		1 4	4 1
	2 3 4 1		3 4 1	4 1 3
	2 4 1 3		1 3	3 1
	2 4 3 1		2 4 3 1	3 1 2 4
	3 1 2 4		2 4	4 2
	3 1 42		1 4 2	2 1 4
	3 2 1 4		1 4	4 1
	3 2 4 1		2 4 1	4 1 2
	3 4 1 2		1 2	2 1
	3 4 2 1		3 4 2 1	4 1 2 3
	4 1 2 3		2 3	3 2
	4 1 3 2		1 3 2	2 1 3
	4 2 1 3		1 3	3 1
	4 2 3 1		2 3 1	3 1 2
	4 3 1 2		1 2	2 1
	4 3 2 1		2 3	3 2

Таким чином маємо 4!=24 перестановки.

Алгоритм 1 зобразимо так:

рис. 4.1. Блок-схема алгоритму 1 побудови перестановок.

Для цього алгоритму треба використати підалгоритм впорядкування деякого буферного масиву, який ми називаємо хвостом перестановки.

Для розгляду другого алгоритму побудови перестановок використаємо

таке поняття, як обертання- це процес, в якому перше число стає на останнє місце.

Таблиця 4.2 Трасування створення перестановок за допомогою алгоритму 2.

№ перестановки	перестановка
	1 2 3 4	m=4:<1 2 3 4>	2 3 4 1
	2 3 4 1	m=4:<2 3 4 1>	3 4 1 2
	3 4 1 2	m=4:<3 4 1 2>	4 1 2 3
	4 1 2 3	m=4:<4 1 2 3> m=3:<l 2 3>	1 2 3 4 (Im=m) 3 1 2 4
	3 1 2 4	m=3:<3 1 2>	2 3 1 4
	2 3 1 4	m=3:<2 3 1> m=2: <1 2>	1 2 3 4 (Im=m) 2 1 3 4

Перестановки дуже важливі для вивчення алгоритмів сортування, тому що вони слугують для подання невпорядкованих вхідних даних. Для аналізу ефективності різноманітних методів сортування треба підраховувати кількість перестановок, які треба повторювати деякий крок алгоритму визначену кількість раз.

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

<== попередня сторінка	\|	наступна сторінка ==>
Перестановка	\|	Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.