3168

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

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

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

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

Русский

2012-10-25

110 KB

149 чел.

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

Дано конечное множество 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.


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


 

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

75697. Стандарт организации 13.06 KB
  Организации могут самостоятельно устанавливать порядок разработки своих стандартов принять документально оформленное решение путем подготовки и утверждения соответствующего организационнораспорядительного документа о признании и применении разработанных ранее и действующих на текущий момент стандартов предприятия или стандартов общественного объединения в качестве стандартов данной организации. Одновременно может быть решен вопрос о целесообразности постепенного поэтапного или одномоментного переоформления стандартов предприятия...
75698. Основные принципы государственной политики в области безопасности (охраны) труда 13.71 KB
  Основные принципы государственной политики в области безопасности охраны труда. Государственная политика в области охраны труда предусматривает совместные действия органов законодательной и исполнительной власти Российской Федерации и республик в составе Российской Федерации объединений работодателей профессиональных союзов в лице их соответствующих органов и иных уполномоченных работниками представительных органов по улучшению условий и охраны труда предупреждению производственного травматизма и профессиональных...
75699. Система управления безопасностью труда на предприятиях лесного комплекса 13.61 KB
  Система управления безопасностью труда на предприятиях лесного комплекса. В системе управления безопасностью труда как и во всякой управляемой системе необходимо определить и четко выделить основные принципы и направления по которым будет осуществляться управляющее воздействие на систему. Схема управления безопасностью труда представлена на рис. ч В формировании здоровых и безопасных условий труда главными направлениями являются следующие: Безопасность производственного оборудования свойство оборудования сохранять соответствие...
75700. Обеспечение здоровых и безопасных условий труда на лесохозяйственном предприятии 11.15 KB
  Обеспечение здоровых и безопасных условий труда на лесохозяйственном предприятии. Основной целью управления безопасностью труда является организация работы по обеспечению безопасности снижению травматизма и аварийности профессиональных заболеваний улучшению условий труда на основе комплекса задач по созданию безопасных и безвредных условий труда. Задачи: создание системы законодательных и нормативных правовых актов в области охраны труда; надзор и контроль за соблюдением законодательных и нормативно правовых актов; оценка и анализ условий и...
75701. Коллективный договор и порядок его заключения 13.99 KB
  Коллективный договор и порядок его заключения Коллективный договор правовой акт регулирующий социально-трудовые отношения в организации и заключаемый работниками и работодателем в лице их представителей. Содержание и структура коллективного договора определяется сторонами. В коллективный договор могут включаться взаимные обязательства работников и работодателя по следующим вопросам: формы системы и размеры оплаты труда; выплата пособий и компенсаций; занятость переобучение; рабочее время и время отдыха включая вопросы...
75702. Обязанности и права работодателя в обеспечении здоровых и безопасных условий труда 13.27 KB
  Обязанности и права работодателя в обеспечении здоровых и безопасных условий труда Основами законодательства Российской Федерации об охране труда определены обязанности работников по соблюдению требований охраны труда и ответственность за нарушение законодательства об охране труда. Работники обязаны: соблюдать нормы правила и инструкции по охране труда; правильно применять средства коллективной и индивидуальной защиты; немедленно сообщать своему непосредственному руководителю о любом несчастном случае происшедшем на производстве...
75703. Обязанности ИТР в обеспечении здоровых и безопасных условий труда 17.81 KB
  Обязанности ИТР в обеспечении здоровых и безопасных условий труда. Инженер по охране труда относится к категории специалистов. Инженер по охране труда назначается на должность перемещается и освобождается от нее приказом руководителя организации по представлению руководителя структурного подразделения. На должность: инженера по охране труда назначается лицо имеющее высшее профессиональное техническое образование без предъявления требований к стажу работы или среднее специальное техническое образование и стаж работы в должности техника...
75704. Обязанности работников в обеспечении здоровых и безопасных условий труда 11.27 KB
  Обязанности работников в обеспечении здоровых и безопасных условий труда. Законодательство об охране труда предусматривает и обязанности работников. Они обязаны соблюдать нормы правила и инструкции по охране труда устанавливающие правила выполнения работ и поведения в производственных помещениях и на строительных площадках использовать и правильно применять коллективные и индивидуальные средства защиты специальную одежду и обувь маски очки респираторы и др. Если правила по охране труда предусматривают что обязательным условием допуска...
75705. Служба инженера по охране труда на лесохозяйственном предприятии 14.1 KB
  Служба инженера по охране труда на лесохозяйственном предприятии В соответствии со статьей 217 Трудового кодекса Российской Федерации в каждой организации осуществляющей производственную деятельность с численностью более 50 работников создаётся служба охраны труда или вводится должность специалиста по охране труда. В организациях с численностью 50 и менее работников решение о создании службы охраны труда принимает работодатель с учётом специфики деятельности данной организации. В случае отсутствия службы охраны труда специалиста...