3168

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

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

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

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

Русский

2012-10-25

110 KB

132 чел.

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

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


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


 

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

51117. Исследование частотных характеристик типовых динамических звеньев 24.84 KB
  Цель работы: исследование амплитудных и фазовых частотных характеристик типовых динамических звеньев. Задачи: Ознакомиться с программой для исследования амплитудной частотной АЧХ и фазовой частотной ФЧХ характеристик типовых динамических звеньев. Произвести снятие частотных характеристик для различных значений параметров.
51119. Реєстрація сигналів в MatLAB 613.88 KB
  Прочитати за допомогою функції load в робочу область сигнал ЕКГ, отриманий з допомогою комп’ютерного електрокардіографа та збережений у mat-файлі. Вивести графік, позначити вісі. (файл архіву ECG_rec.rar на сайті, обрати сигнал згідно номеру за списком; ЕКГ дискретизована з частотою 400 Гц, значення напруги в мілівольтах отримується діленням величин відліків на 500). Визначити (програмно) тривалість записаного сигналу.
51120. Исследование устойчивости системы автоматического регулирования с использованием критериев Гурвица и Михайлова 73.21 KB
  По критерию Михайлова система 1 устойчива график начинается на положительной вещественной полуоси проходит против часовой стрелки 3 квадранта система 2 неустойчива график проходит через 3 квадранта но не против часовой стрелки система 3 устойчива график проходит через точку 00. для системы третьего порядка критерий Гурвица сводится к положительности всех...
51121. Моделювання лінійних систем в часовій та частотній області 500.67 KB
  Сформувати два синусоїдальних сигнали частоти 3 та 20 Гц тривалістю1 с. Проілюструвати властивість адитивності системи, визначивши реакціюсистеми спочатку на кожний з сигналів окремо, а потім на суму цих сигналів.Проілюструвати властивість однорідності системи.
51122. Разработка программы с использованием элементов Radiobutton, Button, Listbox 77.03 KB
  Задание на работу: Разработать программу с использованием элементов Rdiobutton Button Listbox. Предметная область фотопрокат. Код программы (файл Form1.cs)...
51123. Исследование устойчивости системы автоматического регулирования с использованием критерия Найквиста 50.13 KB
  В ходе лабораторной работы был изучен критерий устойчивости Найквиста. Получены АФЧХ разомкнутых систем с астатизмом и без, переходные характеристики замкнутых систем с астатизмом и без. По полученным характеристикам была определена устойчивость систем.
51124. Моделирование непрерывно-стохастической системы массового обслуживания 106.86 KB
  На вход n-канальной СМО с отказами поступает поток заявок с интенсивностью l = 6 заявок в час. Среднее время обслуживания одной заявки 0.8 часа. Каждая обслуженная заявка приносит доход 4у.е. Содержание одного канала обходится 2 у.е./час. Определить экономически целесообразное количество каналов.
51125. Спектральний аналіз сигналів за Фурьє 1.43 MB
  Як відомо, спектри всіх дискретних сигналів періодичні, а амплітудні спектри є парними функціями частоти. Засобами MatLAB можна розрахувати дві половини одного періоду спектру, які є дзеркальними копіями одна одної відносно частоти Найквіста. Через це на всіх графіках амплітудних спектрів достатньо і необхідно виводити лише половину періоду спектру, оскільки вона повністю описує амплітудний спектр