ПЕРЕСТАНОВКИ
Перестановки в математике
Перестановки в математике
Перестановки
без повторения
Перестановками
из n
различных
элементов называются соединения (наборы), каждое (ый) из которых содержит эти n элементов, взятых в определенном порядке.
Замечание.
Перестановкой из n
элементов можно считать установленный в конечном множестве порядок.
Примечание.
Множество называется упорядоченным, если каждому элементу этого множества
поставлено в соответствие некоторое натуральное число (номер элемента) от 1 до N, где N –
число элементов множества, так что различным элементам соответствуют различные
числа.
Очевидно,
что каждое множество, содержащее более одного элемента, может упорядочить не
единственным способом.
Обозначение:
Число
всех перестановок из n
элементов
обозначается Pn
(от
франц. слова «permutation»
- перестановка). Различные перестановки отличаются друг от друга только
порядком расположения элементов.
Вывод
формулы:
Пусть имеется n различных элементов, которые нужно
распределить по n местам и выбор первого элемента можно
осуществить n способами. После выбора первого
элемента второй элемент можно выбрать n – 1 способом (на второе место
можно поставить любой из оставшихся элементов, их осталось n – 1),
третий элемент можно выбрать n – 2 способами и т. д. Последний элемент —
одним способом.
По правилу произведения n элементов можно выбрать способом,
т. е. число способов равно произведению всех натуральных чисел от 1 до n .
Задача.
Сколько различных четырехзначных чисел можно составить из цифр 3, 5, 7, 9 так,
чтобы все цифры были различными?
Решение.
Так как каждое число будет лтличаться от друго только порядком расположения
цифр, то количество чисел, составленных из указанных цифр, будет равно числу
перестановок из 4 элементов. По формуле числа перестановок из n элементов будем иметь P4
= 4! = 24.
На
рисунке 1 показано, как получить перестановки из четырех различных элементов:
На первое место можно поставить любой из четырех элементов (первый столбик), на
второе – любой из оставшихся трех (от каждого выбранного элемента проведены три
стрелки), на третье – любой из
оставшихся двух и т. д.
Если
некоторые из n
элементов
множества равны, т. е. n
= n1
+ n2
+ … + nk,
то
число перестановок из n
элементов
равно:
Рассмотрим перестановку из n элементов,
среди которых некоторые одинаковые, пусть такие n1 – одинаковых. Тогда при перестановке этих n1 элементов между собой перестановка из n элементов
останется той же, а число всех перестановок из n элементов
уменьшится во столько раз, сколькими способами можно переставить n1 элементов, т. е. в n1! раз. Аналогично рассмотренному примеру: если
среди n элементов есть еще n2 – одинаковых, то число всех перестановок из n элементов
уменьшится в n2! раз и т. д. Таким образом, общее число
перестановок из n элементов с повторениями вычисляется по формуле (см. формулу
1.2).
alphabet : string[26] = 'ABCDEFGHIJKLMNOP QRSTUVWXYZ';
var
b : array [1..100] of byte;
N,i,j,k : byte;
Procedure SwapB(i,k:byte);
var x : byte;
begin
x:=B[i]; B[i]:=B[k]; B[k]:=x;
end;
Procedure WriteB;
begin
for i:=1 to N do write({alphabet[b[i]]);
writeln;
end;
begin
readln(N);
for i:=1 to N do b[i]:=i;
WriteB;
while (true) do
begin
i:=N;
while (i>0) and (B[i]>=B[i+1]) do i:=i-1;
if i=0 then exit;
for j:=i+1 to N do
if (B[j]>B[i]) then K:=j;
SwapB(i,k);
for j:=i+1 to (i+ ((N+1-i) div 2))
do SwapB(j,N+i+1-j);
writeB;
end;
end.
В программе, генерирующей все перестановки из N компонент, обозначенных за-главными буквами латинского алфавита введены две процедуры: WriteB и SwapB.
Процедура WriteB вызывается всякий раз, когда построена очередная перестановка. В данной программе процедура WriteB просто выводит соответствующую по-следовательность латинских букв. Процедура SwapB(i,k) введена для упрощения понимания главной программы. SwapB просто обменивает значениями два элемента массива B, которые имеют индексы, соответствующие значениям параметров процедуры i и k.
Процедура SwapB используется в тексте программы два раза:
1) при обмене значениями двух найденных элементов с индексами I и K;
2) при обеспечении попарного обмена элементов «хвоста», в котором текущий элемент с индексом j обменивается местами со своим «партнером», находящимся на позиции N + i + 1 - j. Таким образом, (I + 1)-й элемент поменяется (при J=I+1) местами с N-м элементом, (I + 2)-й элемент (при J=I + 2) - с (N - 1)-м и т. д.
Общее число перестановок из N элементов равно N! (читается - N факториал). Напомним, что N! = 1 * 2 * 3 * ... * N.
Перестановки в информатике
Базовый алгоритм нахождения перестановок
Пусть мы имеем 4 компонента, обозначенные буквами A, B, C, D. Тогда множество всех перестановок из этих компонент будет включать следующие элементы:
ABCD, BACD, CABD, DABC, ABDC, BADC, CADB, DACB, ACBD, BCAD, CBAD, DBAC, ACDB, BCDA, CBDA, DBCA, ADBC, BDAC, CDAB, DCAB, ADCB, BDCA, CDBA, DCBA.
Приведем алгоритм построения следующей перестановки 9 компонент, обозначенных цифрами от 1 до 9. Первая из таких перестановок - это:
ABCD, BACD, CABD, DABC, ABDC, BADC, CADB, DACB, ACBD, BCAD, CBAD, DBAC, ACDB, BCDA, CBDA, DBCA, ADBC, BDAC, CDAB, DCAB, ADCB, BDCA, CDBA, DCBA.
Приведем алгоритм построения следующей перестановки 9 компонент, обозначенных цифрами от 1 до 9. Первая из таких перестановок - это:
1 2 3 4 5 6 7 8 9.
Пусть текущая перестановка из 9 компонент:
1 9 5 8 4 7 6 3 2.
Какой будет следующая перестановка, если мы строим перестановки в лексикографическом порядке (то есть в порядке возрастания величины числа, составленного из этих цифр)? Правильный ответ таков:
1 9 5 8 6 2 3 4 7.
Как он получается? Прежде всего необходимо просматривать исходный массив от конца к началу, чтобы найти первое число, которое меньше предыдущего; в нашем случае - это 4 (7 < 6 < 3 < 2, а 4 < 7). Далее среди просмотренных чисел справа от найденной четверки мы ищем последнее число, которое больше 4. Это число 6 (7 > 4, 6 > 4, 3 < 4, 2 < 4). Затем меняем эти 2 найденных числа (4 и 6) местами и получаем:
1 9 5 8 6 7 4 3 2.
И теперь числа (справа от 6), которые составляют убывающую последовательность (7 4 3 2), попарно меняем местами так, чтобы они составили возрастающую последовательность (2 3 4 7):
1 9 5 8 6 2 3 4 7.
Это и есть следующая перестановка.
А какая перестановка будет последней для данного примера? Надеюсь, что вдумчивый читатель догадался и сам:
А какая перестановка будет последней для данного примера? Надеюсь, что вдумчивый читатель догадался и сам:
9 8 7 6 5 4 3 2 1.
Неформально алгоритм построения очередной перестановки по текущей может быть записан следующим образом:
- От конца к началу перестановки ищем первый элемент B[i] такой, что B[i] < B[i + 1].
- Запоминаем его индекс - I.
- От элемента I + 1 до конца ищем последний элемент, больший, чем B[i], и запоминаем его индекс - K.
- Меняем местами эти элементы с номерами I и K.
- Всю группу элементов от (i + 1)-го элемента до N-го попарно меняем местами: (i + 1)-й элемент с N-м, (i + 2)-й элемент с (N - 1)-м и т. д.
Формализованный алгоритм генерации всех перестановок из N элементов может выглядеть следующим образом:
Ввод N
Прописываем массив B последовательно числами от 1 до N
Это первая - начальная - перестановка, выводим ее
Пока (истина)
i=N
Пока (i>0) и (B[i]>=B[i+1]), i=i-1
Если i=0, то конец работы
Для j от i+1 до N
если B[j]>B[i], то K=j
Обмен значений B[i] и B[k]
Для j от i+1 до (i+ ((N+1-i) div 2))
Обмен значений B[j] и B[N+i+1-j]
Вывод текущей перестановки B
Ввод N
Прописываем массив B последовательно числами от 1 до N
Это первая - начальная - перестановка, выводим ее
Пока (истина)
i=N
Пока (i>0) и (B[i]>=B[i+1]), i=i-1
Если i=0, то конец работы
Для j от i+1 до N
если B[j]>B[i], то K=j
Обмен значений B[i] и B[k]
Для j от i+1 до (i+ ((N+1-i) div 2))
Обмен значений B[j] и B[N+i+1-j]
Вывод текущей перестановки B
Понятно, что цикл парных перестановок «хвоста» массива B нельзя делать от (i + 1)-го до N-го элемента, иначе элементы поменяются местами по два раза и получится, что ничего не изменилось. Цикл нужно выполнить для половины этого «хвоста». Этому и служит несколько сложное для понимания значение конечной переменной цикла: i + (N + 1 - i) div 2.
Алгоритм, генерирующая перестановки из N компонент
constalphabet : string[26] = 'ABCDEFGHIJKLMNOP QRSTUVWXYZ';
var
b : array [1..100] of byte;
N,i,j,k : byte;
Procedure SwapB(i,k:byte);
var x : byte;
begin
x:=B[i]; B[i]:=B[k]; B[k]:=x;
end;
Procedure WriteB;
begin
for i:=1 to N do write({alphabet[b[i]]);
writeln;
end;
begin
readln(N);
for i:=1 to N do b[i]:=i;
WriteB;
while (true) do
begin
i:=N;
while (i>0) and (B[i]>=B[i+1]) do i:=i-1;
if i=0 then exit;
for j:=i+1 to N do
if (B[j]>B[i]) then K:=j;
SwapB(i,k);
for j:=i+1 to (i+ ((N+1-i) div 2))
do SwapB(j,N+i+1-j);
writeB;
end;
end.
В программе, генерирующей все перестановки из N компонент, обозначенных за-главными буквами латинского алфавита введены две процедуры: WriteB и SwapB.
Процедура WriteB вызывается всякий раз, когда построена очередная перестановка. В данной программе процедура WriteB просто выводит соответствующую по-следовательность латинских букв. Процедура SwapB(i,k) введена для упрощения понимания главной программы. SwapB просто обменивает значениями два элемента массива B, которые имеют индексы, соответствующие значениям параметров процедуры i и k.
Процедура SwapB используется в тексте программы два раза:
1) при обмене значениями двух найденных элементов с индексами I и K;
2) при обеспечении попарного обмена элементов «хвоста», в котором текущий элемент с индексом j обменивается местами со своим «партнером», находящимся на позиции N + i + 1 - j. Таким образом, (I + 1)-й элемент поменяется (при J=I+1) местами с N-м элементом, (I + 2)-й элемент (при J=I + 2) - с (N - 1)-м и т. д.
Общее число перестановок из N элементов равно N! (читается - N факториал). Напомним, что N! = 1 * 2 * 3 * ... * N.
Алгоритм генерации перестановок с повторением
(частный случай для трех элементов)
program perebor;
uses crt;
const n=3;
var a : array[1..n] of string;
k : word;
procedure recu(n,m:byte);
var i,j : byte;
s : string;
begin
if m=1 then begin
for i:=1 to n do write(a[i],' ');
writeln;
inc(k);
end else begin
for i:=1 to m do begin
s:=a[1];
for j:=1 to m-1 do a[j]:=a[j+1];
a[m]:=s;
recu(n,m-1);
end;
end;
end;
begin
k:=0;
a[1]:='1';
a[2]:='2';
a[3]:='3';
recu(n,n);
writeln(k,' штук.');
readln;
end.
Комментариев нет:
Отправить комментарий