3168

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

Практическая работа

Информатика, кибернетика и программирование

Генерация перестановок Дано конечное множество A. Требуется сгенерировать все возможные перестановки его элементов в лексикографическом порядке (по материалам главы 1, п. 1.3.6, и главы 2, п. 2.2.1). Требования к заданию множества – в нем не до...

Русский

2012-10-25

110 KB

142 чел.

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

Дано конечное множество A. Требуется сгенерировать все возможные перестановки его элементов в лексикографическом порядке (по материалам главы 1, п. 1.3.6, и главы 2, п. 2.2.1). Требования к заданию множества – в нем не должно быть повторяющихся элементов, кроме того, удобнее использовать или только буквы, или только цифры.

Программа должна сначала упорядочить все элементы заданного множества по возрастанию (это первый – минимальный – набор), затем – посредством МИНИМАЛЬНО ВОЗМОЖНЫХ ПЕРЕСТАНОВОК! – сгенерировать последовательно возрастающие (лексикографически) наборы, вплоть до последнего, в котором все элементы упорядочены по убыванию.

Следует оценивать количество возможных перестановок и в случае, если они не поместятся на экран, выполнять их вывод в файл с выдачей на экран соответствующей информации для пользователя и выполнять поэкранный вывод с ожиданием нажатия клавиши.

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

Возможный алгоритм решения (Пример: множество А={1, 2, 3, 4, 5, 6}, |A| = n):

Предположим, что уже построено m наборов. Тогда для получения m+1-го набора:

  1.  Выполняется проверка последнего (m-го) набора на наличие в его конце некоторого количества символов, упорядоченных по убыванию – пусть это символы ak+1…an.
    á 3 5 2 6 4 1ñ – k=3, символы с 4-го по 6-й упорядочены по убыванию.
  2.  Если такое k найдено, то поменять местами k-й элемент и наименьший элемент из ak+1…an, больший этого ak.
    В нашем примере это 2 и 4:
    á 3 5 4 6 2 1ñ (это промежуточный набор).
  3.  После шага 2 упорядочить элементы с k+1-го до последнего по возрастанию. Получен очередной набор Þ выдать его на печать.
    á 3 5 4 1 2 6ñ.
  4.  Если на шаге 1 ответ отрицательный, то поменять местами 2 последних элемента и выдать на печать полученный набор. В частности, после шага 3 это неизбежное действие, т.к. все последние элементы были размещены по возрастанию Þ целесообразно после выполнения ш.3 задавать признак его выполнения, который будет анализироваться (и сбрасываться) на шаге 1. После шага 3 было á 3 5 4 1 2 6ñ Þ выдать á 3 5 4 1 6 2ñ .
    Если был набор
    á 3 5 2 6 1 4ñ Þ выдать á 3 5 2 6 4 1ñ .
  5.  Если полученный набор не последний (упорядоченный по убыванию), то возврат на шаг 1. В противном случае конец работы.


Решение.

Пусть дано множество , причём все элементы множества сравнимы между собой.

Необходимо получить все перестановки множества . Будем считать, что .

Алгоритм решения.

  1.  Возьмём за первую перестановку последовательность .
  2.  Найдём следующую перестановку. Если её нет, то алгоритм завершён.
  3.  Перейдём к пункту 2.

Алгоритм нахождения следующей (в лексикографическом порядке) перестановки.

  1.  Найдём самый правый , такой, что
  2.  Найдём

  1.  Обменяем местами и .
  2.  Инвертируем подпоследовательность .


Исходный код на Borland Pascal 7.

program lab3;

uses

 Crt;

const

 Output_File_Name = 'output.txt';  { Имя файла, для вывода перестановок }

 Nmax = 12; { Макс. кол-во элементов множества }

type

 T = Char; { Тип элементов множества }

 TArray = Array[1..Nmax] of T;

var

 F: Text;

 Flag: Boolean; { При Flag = True производится запись в файл }

{ Печать перестановки }

procedure Print(const A: TArray; const N: Integer);

var

 i: Integer;

begin

 for i := 1 to N do begin

   Write(A[i], ' ');

   if Flag then Write(F, A[i], ' ');

 end;

 if WhereY = 25 then ReadKey;

 WriteLn;

 if Flag then WriteLn(F);

end;

{ Сортировка выбором по неубыванию }

procedure Sort(var A: TArray; const N: Integer);

var

 i, j, k: Integer;

 tmp: T;

begin

 for i := 1 to N - 1 do begin

   k := i;

   for j := i + 1 to N do

     if A[j] < A[k] then k := j;

   tmp := A[i];

   A[i] := A[k];

   A[k] := tmp;

 end;

end;

{ Генератор перестановок }

procedure Generate(A: TArray; const N: Integer);

var

 p, q, i, k, m: Integer;

 min: T;

 tmp: T;

begin

 while True do begin

   Print(A, N);

   { Ищем крайний справа A[p], такой, что A[p] < A[p+1] }

   p := 0;

   for i := n downto 2 do

     if A[i - 1] < A[i] then begin

       p := i - 1;

       Break;

     end;

   if p = 0 then Exit; { Если не нашли, то все перестановки уже получены }

   { Ищем минимальный A[q] среди A[p+1], ..., A[n], такой, что A[q] > A[p] }

   min := High(min);

   q:= 0;

   for i := p + 1 to N do

     if (min > A[i]) and (A[i] > A[p]) then begin

       min := A[i];

       q := i;

     end;

   { Меняем местами A[p] и A[q] }

   tmp := A[p];

   A[p] := A[q];

   A[q] := tmp;

   { Инвертируем A[p+1], ..., A[n] }

   k := n + (p + 1) - 1;

   m := k div 2;

   for i := p + 1 to m do begin

     tmp := A[i];

     A[i] := A[k - i + 1];

     A[k - i + 1] := tmp;

   end;

 end;

end;

var

 A: TArray;

 N: Integer;

begin

 ClrScr;

 WriteLn('Введите множество элементов через пробел (все элементы должны быть различны).');

 N := 0;

 while not SeekEoLn do begin

   Inc(N);

   Read(A[N]);

 end;

 Sort(A, N);

 Flag := False;

 if N > 3 then begin

   ClrScr;

   WriteLn('Невозможно отобразить все перестановки на экране. Нажмите любую клавишу ');

   WriteLn('для вывода следующей перестановки. Будет произведена запись в файл.');

   Assign(F, Output_File_Name);

   Rewrite(F);

   Flag := True;

 end;

 WriteLn;

 Generate(A, N);

 if Flag then Close(F);

 WriteLn('Выполнено.');

 ReadKey;

end.


Результат работы программы.


 

А также другие работы, которые могут Вас заинтересовать

21188. Ортогональні оператори. Квадратичні формию. Криві другого порядку 282 KB
  2 то одержимо друге означення ортогонального оператора або .3 Звідси маємо для матриці ортогонального оператора або 18.5 показує що рядки стовпці матриці ортогонального оператора ортогональні.1 витікають властивості ортогонального оператора: 1 Якщо ортогональний то і ортогональні.
21189. Криві другого порядку 454.5 KB
  Як було показано в попередній лекції загальне рівняння другого порядку в системі координат побудованій на власних векторах матриці квадратичної форми рівняння має вид 18.1 Спочатку розглянемо випадок коли це рівняння еліптичного або гіперболічного типу тобто . Якщо то рівняння 19. Якщо маємо два рівняння прямих що проходять через новий початок координат .
21190. Поверхні другого порядку 575 KB
  Розглянемо більш загальне рівняння яке містить в собі і квадратичний вираз на предмет того який геометричний обєкт воно описує.1 перетвориться у рівняння 20. В новій системі координат рівняння 20. Перепишемо рівняння 20.
21191. Матриці. Лінійні дії з матрицями. Поняття лінійного простору 207 KB
  Лінійні дії з матрицями. Вона характеризується таблицею чисел яку можна записати окремо і розглядати як суцільний обєкт що має назву матриця лат.2 Очевидно що матриця є узагальненням як числа так і вектора. Дійсно при m=1 n=1 матриця зводиться до числа при m=1 n=3 вона є векторрядок а при m=3 n=1 векторстовпець.
21192. Множення матриць. Поняття детермінанта 255.5 KB
  Множення матриць. Розглянемо якісно нову відмінну від введених в попередній лекції операцій а саме нелінійну операцію множення матриць. Визначити операцію множення матриць це означає вказати яким чином даній парі матриць ставиться у відповідність третя матриця яка і буде їх добутком.
21193. Властивості детермінантів 220.5 KB
  Детермінант транспонованої матриці дорівнює детермінанту даної. З очевидної рівності випливає що детермінант можна записати також у вигляді == =.2 Після транспонування одержимо детермінант в добутках якого індекси множників помінялись місцями.
21194. Логические модели представления знаний 99 KB
  3: sml vrt ktr tnk grz tks объекты; kls vnt krl vgr свойства. Предикаты и константы логической базы знаний Kонстанты Свойства 1 2 3 4 Колеса Винт Крыло Возит грузы kls Vnt krl vgr № Объекты Kонс танты Преди каты R kls R vnt R krl R vgr 1 Самолет sml Qsml Psml kls Psml vnt Psml krl Psml vgr 2 Вертолет vrt Qvrt Pvrt kls Pvrt vnt Pvrt krl Pvrt vgr 3 Катер Ktr Qktr Pktr kls Pktr vnt Pktr krl Pktr vgr 4 Танкер Tnk Qtnk Ptnk kls Ptnk vnt Ptnk krl Ptnk vgr 5...
21195. Алгоритмы решения логических задач 57 KB
  Используя дедуктивную логику из двух или нескольких исходных аксиом имеющихся в логической базе знаний можно вывести очередное утверждениеследствие или доказать истинность ложность целевого утверждения теоремы путем использования определенных правил вывода. Этот процесс получения новых знаний из имеющихся аксиом называют логическим выводом на знаниях. Основными типами логических задач которые решаются с использованием метода резолюций являются следующие: а задача вывода следствий в которой нужно найти все утверждения которые можно...
21196. Семантические сети представления знаний 84 KB
  Семантические сети представления знаний 9. СС это модель представления знаний в которой вся необходимая информация может быть описана в виде совокупности отношений: первый объект бинарное отношение второй объект . Эти отношения образуют иерархическую сеть в которой вершины каждого уровня знаний соединяется линиями с соответствующими вершинами верхнего и нижнего уровней. Проблема поиска решения в семантической базе знаний сводится к задаче поиска фрагмента сети подсети отражающего ответ на запрос пользователя.