Генерирование перестановок.

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

Перестановкой из n элементов называется последовательность, состоящая из всех элементов некоторого n-элементного множества, причем число элементов этой последовательности равно n.

Характерные особенности понятия «перестановка» (существенные признаки понятия):

1. Задано некоторое множество из n элементов.

2. Составляется последовательность из всех элементов этого множества.

3. Эта последовательность содержит n элементов.

Различия и сходства в определениях перестановок и размещений.

· Сходства: перестановки и размещения – это последовательности элементов n-элементного подмножества. В них имеет значение порядок следования элементов последовательности.

· Различия: в размещении могут участвовать не все элементы исходного множества. В перестановке обязательно участвуют все элементы исходного множества.

Число перестановок можно вычислить по формуле P_n=n!

Пример: В расписании сессии 3 экзамена (история, геометрия, алгебра). Сколько может быть вариантов расписаний?

Решение:

Основное множество: {история, геометрия, алгебра} Þ n=3

Соединение – вариант расписания сессии

Проверим, важен ли порядок:

{история, геометрия, алгебра} и {геометрия, история, алгебра} – варианты расписания сессии для разных групп Þ порядок важен Þ это последовательность Þ это размещение «из трех по три» Þ это перестановка из трех элементов.

P₃=3!=6 (вариантов)

Ответ: 6 вариантов

Займемся алгоритмом генерирования всех n! перестановок n-элементного множества. Этой проблеме посвящено много публикаций, она имеет давнюю историю, ее возникновение можно отнести к началу XVII века, когда в Англии зародилось особое искусство колокольного боя, основанного, если говорить упрощенно, на выбивании на n разных колоколах всех n! перестановок. Перестановки эти следовало выбивать «по памяти», что способствовало разработке сторонниками этого искусства первых простых методов систематического перечисления всех перестановок (без повторений). Некоторые из этих незаслуженно забытых методов были переоткрыты в насто­ящее время в связи с появлением цифровых машин.

Сейчас опишем метод генерирования последовательности всех n! перестановок n-элементного множества. Будем предполагать, что элементы нашего множества запоминаются в виде элементов массива Р[1],..., Р[n]. В данном методе элементарной операцией, которая применяется к массиву Р, является поэлементная транспозиция, т.е. обмен значениями переменных P[i] и P[j], где 1 < i,j < n. Эту операцию будем обозначать через Р[i] :=: P[j]. Очевидно, что она эквивалентна последовательности команд роm := Р[i]; Р[i] := P[j]; P[j] := роm, где роm есть некоторая вспомогательная переменная.

Алгоритм. (Генерирование всех перестановок за минимальное число транспозиций.)

Данные: n.

Результат: Последовательность перестановок множества {1,...,n}, в котором каждая последующая перестановка образуется из предыдущей путем выполнения одной транспозиции.

1. procedure В(m, i);

2. begin

3. if (m mod 2=0) and (m > 2) then

4. if i < m — 1 then В := i

5. else В := m — 2

6. else В := m — 1

7. end; (*B*)

8. procedure PERM(m); (* массив P — глобальный*)

9. begin

10. if m = 1 then (*P[1],... ,P[m] — новая перестановка*)

11. write (P[l],...,P[n])

12. else

13. for i := 1 to m do

14. begin PERM(m - 1);

15. if i < m then P[B(m,i)] :=: P[m]

16. end

17. end; (*PERM*)

18. begin (* главная программа*)

19. for i := 1 to n do Р[i] := i;

20. PERM(n)

21. end

Отметим, что для нечетного m транспозиция в строке 15 сводится к Р[m— 1] :=: Р[m], для каждого i < m для четного m значение Р[m] меняется по­следовательно на значения Р[1], Р[2],..., Р[m— 3], Р[m — 2], Р[m — 1] (Р[1] для m-2).