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.


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


 

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

2469. Омоніми та їх використання 25.79 KB
  Мета організації уроку: розширити уявлення учнів про омоніми; поглибити отримані на попередньому уроці знань, навчити учнів розрізняти омоніми, свідомо підходити до розуміння значення і використання омонімів у мовленні.
2470. Групи сполучників за будовою. Конспект уроку 23.85 KB
  Мета організації уроку: згадати про службові частини мови, а саме про сполучник, сформувати в учнів поняття про класифікації сполучників, зокрема за будовою.
2471. Неозначені й заперечні займенники, їх утворення. Дефіс у неозначених займенниках 23.9 KB
  Мета організації уроку. Дати відомості про творення та вживання неозначених і заперечних займенників, формувати вміння визначити орфограми Дефіс у неозначених займенниках та обгрунтувати вибір написання відповідними орфографічними правилами, розвивати зорову і слухову увагу,спостережливість, культуру усного і писемного мовлення.
2472. Правопис прислівників. – Н і нн у прислівниках 15.86 KB
  Мета: ознайомити учнів з правилами написання прислівників на - е, -о, пояснити причини написання -н та –нн прислівниках, формувати уміння, знаходити орфограми одна і дві букви н у прислівниках, правильно писати слова з виучуваною орфограмою, на основі попередньо засвоєних знань з теми Прислівник як частина мови.
2473. Оборудование, механизация и автоматизация сварочного производства 391.59 KB
  Данный сборник направлен на формирование умений применять полученные знания на практике, на реализацию единства интеллектуальной и практической деятельности. Механизация и автоматизация являются важнейшим средством повышения производительности труда, улучшения качества и условий труда в сварочном производстве.
2474. Теория электрических цепей. Автогенераторы 895.56 KB
  Изучение и компьютерное моделирование работы LC-автогенератора с трансформаторной обратной связью. В работе необходимо исследовать условия самовозбуждения автогенератора, а также научиться определять амплитуду напряжения на выходе автогенератора в стационарном режиме.
2475. Фінанси. Електронний курс лекцій 544.17 KB
  Сутність фінансів, їх функції і роль. Принципи структурування фінансової системи. Організаційна структура фінансової системи. Управління фінансовою системою та фінансова політика. Зовнішні і внутрішні фінансові відносини. Суть і склад державних фінансів. Бюджет держави: сутність і призначення. Пряме та непряме оподаткування в Україні. Страхування і страховий ринок. Визначення фінансового ринку і його елементи.
2476. Економічна статистика 731 KB
  Основи класифікації економічної статистики. Система національних рахунків – методологічна основа економічної статистики. Показники статистики населення. Завдання статистики населення. Показники чисельності та складу населення. Статистика використання робочого часу. Статистика науково-технічної та інноваційної діяльності. Оцінка рівня інфляції, її використання для порівняльного аналізу вартісних показників. Статистика доходів сектору домашніх господарств. Джерела інформації про споживання населенням.
2477. Основы аудита. Принципы профессиональной этики аудита 244 KB
  Структура договора на проведение аудиторской проверки. Предплановая (преддоговорная) деятельность. Документация аудитора. Обзор событий, произошедших после даты составления баланса. Планирование аудиторской проверки, ее назначение и принципы. Критерии отнесения организации к обязательному аудиту. Основные этапы становления и развития аудита в России.