3168

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

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

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

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

Русский

2012-10-25

110 KB

136 чел.

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

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


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


 

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

23014. Проблема походження мови, основні теорії походження мови 43.5 KB
  Проблема походження мови основні теорії походження мови. Проблема походження мови є дуже складною. проблему походження мови порушувалася в межах філософських дискусій про сутність мови. Представники школи Платона вважали що назви предметам даються не довільно а відповідно до їх Природи що свідчить про природний характер мови і відповідно закономірну біологічну зумовленість її виникнення.
23015. Синтагматичний та парадигматичний аспекти дослідження мовних одиниць 28 KB
  Синтагматичний та парадигматичний аспекти дослідження мовних одиниць. Синтагматика один із двох системних аспектів у вивченні мови який розглядає відношення між послідовно розташованими одиницями за їхнього безпосереднього поєднання в реальному потоці мовлення або в тексті тобто сполучуваність мовних одиниць. Парадигматична методика охоплює опозиційний прийом на основі зіставлення і протиставлення мовних одиниць встановлюються їх диференційні ознаки а на основі спільності й відмінності одиниці об'єднуються в різні парадигматичні...
23016. Фактори розвитку мов. Поняття національна мова, літературна мова 29 KB
  Поняття національна мова літературна мова. Літературна мова унормована мова суспільного спілкування загальноприйнята в писемній та усній практиці. Літературна мова одна із форм національної мови що існує поряд з іншими її формами діалекти просторіччя мова фольклору.мови нормованість кодифікованість полі функціональність загально значущість наявність не тільки писемного а й усного різновиду.
23017. Семіотика як наука про знакові системи 35 KB
  Вивчення мови на рівних правах і тотожними методами мислиться в складі семіології єдиної науки про знаки. За першою класифікацією всі знаки поділяють на знакиіндекси знакикопії знакисигнали і знакисимволи. Знакиіндекси знакиприкмети і знакисимптоми знаки пов'язані з позначуваними предметами як дії зі своїми причинами. Знакикопії відтворення репродукції подібні на позначувані предмети.
23018. Мова як особлива знакова система 34 KB
  Мова як особлива знакова система. Знак матеріальний чуттєво сприйманий предмет який є представником іншого предмета і використовується для отримання зберігання і передачі інформації У світі існують різноманітні системи знаків які служать для передачі інформації. Серед них наприклад дорожні знаки морська сигналізація прапорцями та інші знаки. Основними ознаками знака є матеріальність його можна бачити чути тобто сприймати органами чуттів використання його для позначення чогось що перебуває поза ним інформативність.
23019. Основні властивості знаків, мовних знаків 34.5 KB
  Основні властивості знаків мовних знаків. Про довільність мовних знаків свідчить той факт що одні й ті ж поняття в різних мовах передаються різними словами укр. До вмотивованих мовних знаків передусім належать звуконаслідувальні слова типу бух ляп хлоп хіхікати. Саме завдяки цьому асиметричному дуалізмові структури знаків лінгвальна система може еволюціонувати.
23020. Мова і мовлення 32 KB
  Мова і мовлення Мова система одиниць спілкування і правил їх функціонування. Іншими словами мова це інвентар словник і граматика які існують у потенції в можливості Мовлення конкретно застосована мова засоби спілкування в їх реалізації. Усе те що пересічні мовці розуміють під словом мова насправді є власне мовою і мовленням. Розмежування мови і мовлення теоретично обґрунтоване швейцарським лінгвістом Ф.
23021. Мова, мислення, свідомість 35 KB
  Мова мислення свідомість Мислення узагальнене й абстрактне відображення мозком людини явищ дійсності в поняттях судженнях й умовиводах. Щодо мови і мислення в науці існували два протилежні й неправильні погляди ототожнення мови й мислення Д. Гаман і відривання мови від мислення Ф. Представники першої точки зору вважали що мова це всього лише форма мислення.
23022. Мовна система та структура 33 KB
  Мовна система та структура Система мови множинність елементів будьякої природної мови які перебувають у відношеннях і звязках один з одним і утворюють певну єдність і цілісність. Структура мови спосіб організації мовної системи її внутрішня будова. У науковій літературі немає чіткої диференціації термінів система і структура. Реформатський який запропонував термін система використовувати для позначення системних відношень між одиницями одного рівня мови а термін структура для визначення системних відношень між різними рівнями.