3168

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

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

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

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

Русский

2012-10-25

110 KB

140 чел.

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

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


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


 

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

84127. Классификация государств, её основания и значение. Место и роль типологии государств в системе классификации государств 23.92 KB
  Ленина и других решающим фактором общественного развития который детерминирует и соответствующий тип надстроечных элементов: государство и право. Рабовладельческое государство есть орудие поддержания власти рабовладельцев над рабами которые были собственностью свободных граждан. Феодальное государство это диктатура класса феодалов земельных...
84128. Развитие идей русской религиозной философии в рамках «метафизики всеединства» конца XIX - первой половины XX столетия (В. Соловьев, Н. Бердяев, С. Булгаков, П. Флоренский, С. и Е. Трубецкие) 36.64 KB
  Эта характерная черта русской религиозной философии была задана философской СИСТЕМОЙ ВСЕЕДИНСТВА ВЛАДИМИРА СОЛОВЬЕВА. По Соловьеву всеединство это органическое единство всего мира которое осуществляется в двух видах: 1. Следовательно у всего мира есть нечто внешнее ему некое Всеединство общее для всех его частей которое своим действием образует из множества отдельных и не причастных друг к другу частей единый мир. Следовательно Всеединство образуя из множества частей единое давая всем частям мира истинное и полноценное совместное...
84129. Русская идея как основная проблема отечественной философии истории (В.С. Соловьев, Н.А. Бердяев, И.А. Ильин) 36.2 KB
  Помимо святости как государствастолпа истинного христианства исключительность России Николай БЕРДЯЕВ обосновывал особенностями русского национального характера особенностями русской души. Это сняло с русского человека чувство личной ответственности за вопросы государственного характера и определило такие стороны его характера как: слабое осознание личных прав и личных интересов; равнодушие к политике и к политическим идеям; беспечность и лень; недостаток инициативы и самодисциплины. Восточный византийский склад характера устремляет...
84130. Космизм в русской философии (Н.Ф. Федоров, К.Э. Циолковский, А.О. Чижевский, В.И. Вернадский). Его основные положения 39.58 KB
  Его основные положения В русской философии XIX века сформировался так называемый русский космизм направление мысли пытающееся в глобальном смысле гармонизировать мир соединением человека с космосом. Истоки русского космизма как и сама его логика находились в представлениях о зависимости жизни человека от характера физических параметров ближнего космоса и вообще всей Вселенной: 1. Кроме того исходя из подобного предположения мы можем предположить и следующее глобальные процессы во Вселенной определяют и биологическую жизнь человека...
84131. Марксистская философия в России, легальное и революционное направления (П.Б. Струве, М.И. Туган-Барановский, Г.В. Плеханов, В.И.Ленин) 35.94 KB
  В противоборстве идей славянофилов и западников в России в конечном итоге победила западная ориентация которая тяготела к идеям популярного в то время в Европе марксизма. ЛЕГАЛЬНЫЕ МАРКСИСТЫ отрицали любое насилие в политическом процессе утверждали перспективность капитализма для России и предлагали совершенствовать общество путём демократических реформ. Основателем и первым идеологом легального марксизма в России стал Петр СТРУВЕ.
84132. Бытие, материя, природа как определяющие онтологические категории. Их взаимосвязь и различие 37.43 KB
  Бытие существующее сущее это действительность как таковая это всё то что реально существует. Изучением Бытия занимается раздел философии онтология поэтому Бытие как онтологическая категория выражает в философии ту сферу реальности которая не относится к процессам сознания и психики человека сфера гносеологии. Таким образом Бытие это онтологическая категория выражающая собой всё что объективно существует в мире вне сознания человека и вообще никак не зависит ни от сознания ни от воли ни от эмоций человека. Вследствие этого...
84133. Движение. Движение как способ существования материи. Становление, изменение, развитие. Основные формы движения 36.02 KB
  Основные формы движения. В таком случае само понятие движения изменения изменчивости можно понимать только относительно некоего момента устойчивости относительно некоего момента покоя содержащего в себе набор характеристик относительно которых возникает картина происходящих изменений. Следовательно само состояние устойчивости объектов систем или явлений само состояние стартового покоя от которого начинается и усматривается их изменение находится также в составе самого движения поскольку движение никогда нигде не исчезает и не...
84134. Пространство и время. Пространство и время как всеобщие формы существования материи. Принцип единства мира 32.48 KB
  Пространство и время как всеобщие формы существования материи. Концепции нераздельного с материей пространства могут предлагать его не только трехмерным но и четырехмерным например релятивизм длина ширина высота время или nмерным в еще больших количествах где каждое новое измерение отводится для того или иного отдельного физического взаимодействия фундаментального характера современные физические модели наподобие теории струн и пр. Время это некая мыслимая целостность вбирающая в себя длительность некоего движения и маркирующая...
84135. Проблемы сознания в философии. Язык и мышление как формы объективизации сознания. Их соотнесенность 36.48 KB
  Язык и мышление как формы объективизации сознания. Основной проблемой сознания в философии является вопрос его отношения к бытию. Этот вопрос имеет две стороны: онтологическую в рамках которой решается вопрос первичности материи или сознания по отношению друг к другу и гносеологическую в рамках которой решается вопрос о принципиальной возможности познания мир.