Перестановки


Скачать 346.8 Kb.
НазваниеПерестановки
страница1/7
Дата публикации26.05.2014
Размер346.8 Kb.
ТипДокументы
referatdb.ru > Астрономия > Документы
  1   2   3   4   5   6   7

Перестановки



Соединения, каждое из которых содержит n различных элементов, взятых в определенном порядке, называются перестановками из n элементов. Следует отметить, что порядок элементов в перестановке существенен и в образовании перестановки участвуют все n элементов (m = n).

Пример. Выпишем все перестановки из элементов a, b, c.

abc, acb, bac, bca, cab, cba.

Количество всех способов, которыми можно переставить n различных предметов, расположенных на n различных местах принято обозначать Pn (читается "число перестановок из n").

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

Пример. Сколько всего шестизначных четных чисел можно составить из цифр 1, 3, 4, 5, 7 и 9, если в каждом из этих чисел ни одна цифра не повторяется.

Последняя цифра четного числа должна быть четной, поэтому в данном случае последней цифрой числа может быть только цифра 4. Оставшиеся пять цифр могут стоять на оставшихся пяти местах в любом порядке. Поэтому количество способов их расстановки равно P5 = 5! = 120.

Иногда требуется не просто подсчитать количество перестановок из n элементов, но и найти каждую из них.

Существует несколько алгоритмов генерации всех перестановок из n элементов. Они различаются порядком получения перестановок.

Рассмотрим один из хорошо известных алгоритмов, в процессе исполнения которого перестановки n чисел располагаются лексикографически (в словарном порядке). Это значит, что перестановки сравниваются слева направо поэлементно и большей из них является та, у которой раньше встретился элемент, больший соответствующего ему элемента во второй перестановке. (Например, если S = (3, 5, 4, 6, 7), а L = (3, 5, 6, 4, 7), то S < L).

Опишем алгоритм для n = 5, от чего рассуждения не утратят общности. В дальнейшем, для удобства, будем работать не с самими элементами, а с их номерами (от 1 до n).

Принцип работы алгоритма разъясним на примере. Допустим, необходимо воспроизвести все перестановки чисел 1, 2, 3, 4, 5. Первой перестановкой считаем перестановку (1, 2, 3, 4, 5). Последней перестановкой будет (5, 4, 3, 2, 1). Элементы перестановки будем хранить в массиве.

Предположим, что на некотором шаге работы алгоритма получена перестановка P:

P = (3, 4, 5, 2, 1) = (p1, p2, p3, p4, p5).

Для того чтобы определить непосредственно следующую за ней перестановку, необходимо выполнить следующие шаги:

Шаг 1. Будем просматривать данную перестановку справа налево и следить за тем, чтобы каждый следующий элемент перестановки (элемент массива с большим номером) был больше предыдущего (т. е. элемента массива с меньшим номером), и остановиться сразу же, как только это правило нарушится (1 < 2 < 5, а 5 > 4). Место останова указано подчеркиванием:

(3, 4, 5, 2, 1).

Шаг 2. Затем вновь просматриваем пройденный путь (справа налево) до тех пор, пока не дойдем до первого числа, которое уже больше отмеченного. Место второго останова отмечено двойным подчеркиванием.

(3, 4, 5, 2, 1).

Шаг 3. Поменяем местами отмеченные числа:

(3, 5, 4, 2, 1).

Шаг 4. В части массива, расположенной справа от двойного подчеркивания, упорядочим все числа в порядке возрастания. Так как до сих пор они были упорядочены по убыванию, то это легко сделать, записав в обратном порядке указанную часть массива. Получим новую перестановку, которую обозначим Q = (q1, q2, q3, q4, q5):

Q = (3, 5, 1, 2, 4).

Эта и есть та перестановка, которая непосредственно следует за ^ P в лексикографическом порядке.

В массива P будем хранить номера элементов. В начале в массиве хранятся числа от 1 до n, расположенные в порядке возрастания, так что каждый элемент равен своему номеру. Нулевой элемент фиктивный, он используется для проверки окончания работы. Генерация перестановок будет закончена, когда нулевой элемент станет отличным от нуля.

Запишем алгоритм генерации перестановок:

program Perestanovka;

Var b,p,r:array[0..50] of integer;

k,kol,i,j,n:word; d:integer;

begin

readln(n); kol:=0;

for i:=1 to n do read(b[i]);

for i:=0 to n do p[i]:=0;

While p[0]=0 do

begin

for i:=1 to n do

write(b[p[i]]); writeln;

j:=n;

While p[j-1]>p[j] do

j:=j-1;

k:=n;

While p[j-1]>p[k] do

k:=k-1;

d:=p[j-1];

p[j-1]:=p[k];

p[k]:=d;

for i:=j to n do

r[i]:=p[n-(i-j)];

for i:=j to n do

p[i]:=r[i];

kol:=kol+1;

end;

writeln(kol)

end.

  1   2   3   4   5   6   7

Похожие рефераты:

Вопросы к зачету по алгебре и геометрии поит (1 семестр)
Перестановки. Знак перестановки. Симметрическая и знакопеременная группы степени n
Задача № Перестановки цифр
А1; А2 = M1 – m1 (А2 рассматриваем как n-значное число). По аналогии с А2 определяем числа А3 = M2 – m2, А4 = M3 – m3 и т д
Technical data ena 9 Ключевые технологии
Приготовление капучино, латте маккиато одним нажатием кнопки, без перестановки чашки 
Тематика курсовых работ для студентов 4 курса специальности «Классическая филология»
Фигуры убавления, размещения, перестановки в античной и византийской риторических традициях

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза