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.


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


 

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

33265. Основные положения по проектированию организационных структур управления 35 KB
  Заключается в разумной централизации функций работников в отделах и службах предприятия с передачей в нижнее звено функции оперативного управления. Обеспечивается закреплением за каждым подразделением определенных функций управления. Характеризует достижение минимально необходимых затрат на построение и содержание организационной структуры управления.
33266. Предмет науки управления (менеджмента) 41.5 KB
  Содержание функций управления. Менеджмент это процесс управления руководства отдельным работником рабочей группой коллективом для достижения цели организации. Менеджмент подразумевает определенную категорию людей получивших профессиональное образование в сфере управления и практически занимающихся руководством.
33267. Характеристика основных принципов управления организацией 58.5 KB
  творчества менеджеров основаны на определенных законах Законы управления Законы управления Содержание 1. Организация управления 4. Законы присущие всем сторонам управления 1.
33268. Эволюия основных подходов к менеджменту, характеристика школ 49 KB
  Эволюия основных подходов к менеджменту характеристика школ Основные положения школ менеджмента: Школа научного управления. Школа административного управления. Ее основные принципы: Развитие принципов управления. Описание функций управления.
33269. Характеристика современных концепций менеджмента (системный , ситуационный , количественные подходы). Сущность целевого и стратегического подхода в менеджменте 30.5 KB
  При ситуационном подходе возникшем в конце 60х годов не считается что концепции традиционной теории управления. школы человеческих отношений и школы науки управления неверны. Считая концепцию процесса управления применимой ко всем организациям сторонники ситуационного подхода нашего столетия признают что. хотя общий процесс одинаков специфические приемы которые должен использовать руководитель для эффективного управления могут значительно варьироваться.
33270. Классификация и общая характеристика управления методов управления персоналом 56.5 KB
  Классификация и общая характеристика управления методов управления персоналом Управление персоналом как специфическая деятельность осуществляется с помощью различных методов способов воздействия на сотрудников. Экономические методы Экономические методы управления являются способами воздействия на персонал на основе использования экономических законов. Наиболее распространенными формами прямого экономического воздействия на персонал являются: хозяйственный расчет материальное стимулирование и участие в прибылях через приобретение ценных...
33271. Управленческое решение: содержание, виды . Стадии и технологии принятия управленческих решений 68.5 KB
  Классификация управленческих решений Классификационный признак Группы Управленческих решений Степень повторяемости проблемы Традиционные Нетипичные Значимость цели Стратегические Тактические Сфера воздействия Глобальные Локальные Длительность реализации Долгосрочные Краткосрочные Прогнозируемые последствия решения...
33272. Элементы налога на имущество организаций и их характеристика 26 KB
  Элементы налога на имущество организаций и их характеристика. Налог на имущество организаций является наиболее весомым в региональных налогах. Плательщиками налога на имущество являются: организации включая банки и кредитные учреждения в том числе с иностранными инвестициями являющиеся юридическими лицами в соответствии с законодательством РФ; филиалы и другие аналогичные подразделения организаций имеющие отдельный баланс и расчетный счет; организации с иностранными инвестициями иностранные компании фирмы международные объединения и...
33273. Элементы транспортного налога и их характеристика 25.5 KB
  Объектом налогообложения являются транспортные средства подлежащие регистрации в соответствии с постановлением Правительства РФ №938 от 12. Налоговой базой является мощность двигателя которая указана в технологическом паспорте транспортного средства в лошадиных силах или киловаттах мощности. Налог исчисляется в рублях с каждой лошадиной силы киловатта мощности каждого транспортного средства по ставкам. Налог уплачивается раз в год по месту нахождения плательщика или регистрации транспортного средства и зачисляется в территориальный...