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.


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


 

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

36406. Приведите классификацию, структурную схему импульсной САУ. Поясните преобразования сигнала при модуляции и демодуляции и формирование закона управления 66.39 KB
  Оно во многих случаях по эффективности совпадает с цифровыми то есть имеет те же преимущества но формирует на объект воздействие импульсное то есть электродвигатели работают в импульсном режиме что дает энергетические преимущества то есть делает САУ экономичными. ИМ импульсный модулятор ВУ вычислительное устройство ИД импульсный демодулятор ИМ импульсный модулятор АИМ: В САУ с АИМ в качестве демодулятора используются электродвигатели исполнительных механизмов которые являются обязательными элементами любой САУ.
36407. Разработайте и поясните эквивалентную расчетную схему дискретной САУ 20.14 KB
  При разработке расчетной схемы будем использовать допущения: Операция квантования по уровню нелинейна = ЦСАУ нелинейна. Операция дискретизации сигнала линейна поэтому в дальнейшем нелинейные ЦСАУ заменим дискретными линейными САУ. В этой схему удобно объединить два блока работающих в непрерывном режиме Получена расчетная схема ЦСАУ эквивалентная по дискретной составляющей исходной САУ с цифровым регулятором. Эта схема позволяет ввести понятие переходной функции ЦСАУ в дискретном пространстве.
36408. Поясните понятие устойчивости дискретной САУ. Дайте классификацию методов определения устойчивости и поясните их 64.92 KB
  Дайте классификацию методов определения устойчивости и поясните их. единичная окружность zплоскости представляет собой границу устойчивости. Такое состояние называется апериодическая граница устойчивости.
36409. Выведите формулы спектра дискретного сигнала и проанализируйте его свойства 27.04 KB
  Спектральная плотность дискретного сигнала xTjω будем называть спектром дискретного сигнала. Спектр дискретного сигнала в отличие от аналогового периодичен по частоте с периодом fдискр. k=0123∞ Периодизация спектра обусловлена дискретизацией сигнала по времени.
36410. Приведите алгоритм дискретной обработки и получите передаточные функции и импульсную характеристику дискретной САУ 535.95 KB
  При построении дискретной САУ реализуется 2 подхода: Частота с которой ПК рассчитывает процессы так велика что интервал гораздо меньше всех постоянных времен НЧ. Если при этом и шаг квантования мал то САУ практически не отличается от непрерывной системы и если исполнительный механизм и объект меняются то и цифровая САУ меняется. В этом случае САУ нужно считать дискретными и процессы в них необходимо описывать с применением специального математического аппарата.
36411. Поясните способы определения выходного сигнала в дискретной САУ 148.07 KB
  1 способ: Перейти от к можно несколькими способами 2 способ: представить zпреобразование выходного сигнала: по таблице Анализ: 1 Первый способ более простой однако он обладает двумя недостатками: При делении полиномов получаются бесконечные ряды. Для получения приемлемого резта необходимо рассчитать большое количество членов ряда Если интеграл дискретизации выбран неверно то произойдет наложение спектральных составляющих которые существенно исказит выходной сигнал 2Преимущество второго способа состоит в том что сразу получается...
36412. Системы подчиненного регулирования параметров электропривода 25.03 KB
  Системы подчиненного регулирования параметров электропривода. ‘ возможность ограничить любой параметр на любом уровне Система с последовательной коррекцией или система подчиненного регулирования СПР удобны в расчетах и в настройках характерным является то что даже при существующих ошибках в определении параметров объекта системы остаются работоспособными и обладают запасом устойчивости и точности. Каждому регулируемому параметру соответствует свой датчик регулятор и контур регулирования. Контура регулирования вложены друг в друга...
36413. Приведите нелинейные модели САУ 16.25 KB
  Каждая СУ состоит их линейных и НЛЗ. Наличие одного НЛЗ делает всю САУ нелинейной. По матму описанию процессов НЛЗ делятся на статиче и динамиче. Описывся алгебраичми зависимочтями выхй величины от вхй Динамиче НЛЗ процессы котх описся НЛ ДУ например: Принципы нелинейности: а коэфты уря зависят от перх б степень произвх выше 1 и самой произвой в коэфт К зависит от самой производной ДУ будет НЛ если присутт хотя бы один из признаков нелинейности.
36414. Способы определения параметров динамических моделей 21.97 KB
  В зависимости от вида переходной характеристики кривой разгона задаются чаще всего одним из трех видов передаточной функции объекта управления: в виде передаточной функции инерционного звена первого порядкагде K T и коэффициент усиления постоянная времени и запаздывание которые должны быть определены в окрестности номинального режима работы объекта.Для объекта управления без самовыравнивания передаточная функция имеет вид: Более точнее динамику объекта описывает модель второго порядка с запаздыванием Экспериментальные методы определения...