Материал: 24_41

-змінити початковий стан елементів послідовності на та­ кий, що розташований за спаданням;

-перегляд елементів поточної послідовності здійснювати зліва направо, визначаючи при цьому перший елемент, на яко­ му відбувається порушення спадання;

-переглядаючи послідовність зліва направо, визначити перший елемент, який більший за визначений у попередньому кроці, для наступного їх обміну місцями;

-упорядкувати всі елементи послідовності, що знаходяться на її початку, до елемента, визначеного у другому пункті цього алгоритму, за спаданням.

Завершимо знайомство з алгоритмом перестановок питання­ ми його тестування. Правильно складений алгоритм, тобто перевірений на невеликій множині елементів, гарантовано дає такий самий результат і на будь-якій іншій за кількістю еле­ ментів множині. Тому достатньо перевірити його роботу, на­ приклад, для N = 4 та значень елементів 1, 2, 3, 4, оскільки та­ ку кількість перестановок не складно проконтролювати. Ціка­ вою також є перевірка роботи алгоритму для інших значень елементів: символів, слів тощо.

Завдання

1.Розробити і реалізувати у вигляді програми алгоритм визна­ чення кількості всіх можливих перестановок.

2.Розробити і реалізувати у вигляді програми алгоритм гене­ рації всіх можливих варіантів перестановок.

3.Виконати завдання 1 та 2 для множини елементів 1, 2, 3, 4, 5, вивівши результат виконання програми у файл.

4.Модифікувати та реалізувати у вигляді програми алгоритм завдання 2 для випадку, коли варіанти перестановок форму­ ються у зворотному лексикографічному порядку.

5.Виконати завдання 4 для множини елементів 1, 2, 3, 4, 5, вивівши результат виконання програми у файл.

6.Модифікувати програми у завданнях 2-5 для множини різних символів.

7.Модифікувати програми у завданнях 2-5 для множини різних слів.

8.Зробити письмовий аналіз виконання завдань 1-7.

29

Сполучення

Перейдемо до питання визначення кількості способів, якими можна вибрати М із N різних елементів, а також і самих усіх можливих варіантів сполучень. Для цього скористаємося поняттям сполучення або вибірки (ft-combination).

Для обчислення кількості сполучень можна скористатися

раніше наведеною формулою: С% ==——— —-. Як бачимо, знову

Ml(N-M)l

маємо справу з обчисленням факторіала, а це означає, що навіть із незначним збільшенням значення N кількість сполучень значно зростає.

У разі, коли задача вимагає не тільки обчислення кількості сполучень, а ще й визначення всіх можливих варіантів вибору М різних елементів з N заданих, її можна звести до попередньої задачі про перестановки. Пояснимо хід таких міркувань.

Позначимо ті елементи, які будемо вибирати із заданого на­ бору, цифрою 1, а ті, які не вибираємо, - 0. Нехай нам задано 5 елементів, а треба вибрати будь-яких 3. Один із варіантів вибірки буде виглядати так: 10110. Це означає, що ми підго­ тували послідовність-маску, яка допомагає нам вибрати у дано­ му випадку перший, третій і четвертий елементи із 5 заданих. Можливий і такий варіант: 11100. У цьому разі ми вибрали три перших елементи із 5 заданих. Логіка підказує, що можна переставляти цифри 1 у п'яти заданих позиціях послідовностімаски певним чином до того часу, поки не одержимо комбіна­ цію 00111. Одержати всі необхідні нам варіанти можна за допо­ могою алгоритму побудови перестановок елементів множини, що складаються з 0 та 1, тобто вишикувавши їх у такому лекси­ кографічному порядку:

11100, 11010, 11001, 10110, 10101, 10011, 01110, 01101, 01011,00111.

Зверніть увагу на те, що у даному алгоритмі ми змінили лек­ сикографічний порядок перестановок у послідовності-масці, вишикувавши їх у порядку спадання. Це пов'язано з тим, що саме таким чином ми одержимо результат вибірок із заданої множини в лексикографічному зростаючому порядку.

Сформулюємо алгоритм отримання вибірки М із N різних елементів у загальному випадку.

1.Спочатку необхідно визначити стартову позицію розмі­ щення елементів: І.-.ІОдЛ).

МN-M

2.Далі застосувати алгоритм для визначення всіх можли­ вих перестановок цих елементів для визначення тих елементів заданої множини, які входять до поточної вибірки.

ЗО

3. Завершенням роботи алгоритму є ознака отримання ос­ танньої перестановки: 0...01..1.

N-М М

Наведемо фрагмент тексту Pascal-програми, що реалізує сформульований алгоритм:

for і := 1 to n - m do а[і] := 0;

for і := п - m + 1 to n do a[i]:=1;

for і := 1 to n do {Виведення першого варіанта перестановки заданих елементів.} ifa[i]=1 thenwrite(b[i],'');

writeln;

ifa[i] = 1 thenwrite(b[i], " ) ; writeln;

end;

Однак слід зазначити, що для коректної роботи цього алго­ ритму необхідно дещо модифікувати процедуру організації пе­ рестановок. Це пов'язано з тим, Що елементами масиву а[і] є цифри 0 та 1, а в оригінальній процедурі ми розглядали різні за значеннями елементи. Крім цього, для отримання послідовнос­ тей вибірок у зворотному лексикографічному порядку необ­ хідно поміняти і знаки відношень між елементами, значення яких порівнюються.

Модифікований варіант процедури організації перестановок може виглядати так:

procedure perm; var і, k, с: byte; begin

i:=n;

while a[i - 1] >= a[i] do dec(i); k : = i - 1 ;

i:=n;

while a[i] <= a[k] do dec(i); c := a[kj; a[k] := a[i]; a[i] := c; fori:=1 t o ( n - k ) d i v 2 d o

begin

|c:=a[k + i];a[k + i] :=a[n -i + 1];a[n-i + 1] :=c end;

end;

31

Враховуючи наведену вище формулу для підрахунку кіль­ кості варіантів визначених вибірок із заданої множини для ви­ падку М < 0,5N, можна запропонувати таку послідовність дій для її обчислення, попередньо спростивши її до вигляду:

М !

f := 1;

for і := n - m + 1 to n do f : = f * i ;

f1 : = 1 ;

for і := 1 to m do f1 :=f1 * i ;

f := f div f 1; {Використовуємо div для отримання цілого результату.}

Як і у випадку з перестановками, достатньо перевірити ко­ ректність роботи програми, що реалізує алгоритм визначення заданих вибірок, для N = 4 та значень елементів 1, 2, 3, 4. Тоб­ то тестування алгоритму зводиться до перевірки коректності його роботи на невеликій множині числових елементів. По­ дальше тестування можна провести для більших значень з ме­ тою порівняння часу виконання алгоритму та для елементів, значеннями яких є символи, слова тощо.

Завдання

1.Розробити і реалізувати у вигляді програми алгоритм визна­ чення кількості всіх можливих вибірок.

2.Розробити і реалізувати у вигляді програми алгоритм фор­ мування всіх можливих варіантів вибірок.

3.Виконати завдання 1 та 2 для множини елементів 1, 2, 3, 4, 5 та М = 3, вивівши результат виконання програми у файл.

4.Модифікувати програми у завданнях 2-4 для множини різ­ них символів.

5.Модифікувати програми у завданнях 2-4 для множини різ­ них слів.

6.Зробити письмовий аналіз виконання завдань 1-5.

Розміщення

Як і для попередніх елементів комбінаторики, визначимо можливість одержання кількості способів, якими можна ви­ брати М із N різних предметів і розмістити їх на М місцях, та самих цих розміщень, для чого скористаємося розміщенням. Розміщення елементів без повторень (fe-permutation) - це кіль­ кість способів, якими можна вибрати М із N різних предметів і розмістити їх на М місцях. Така задача зводиться до двох

1Якщо М > 0,5N, то раціональніше спростити вираз до вигляду:

„_ ( М + 1)(М + 2)-...М

(N-M)l

32

попередніх: необхідно зробити всі можливі вибірки М елемен­ тів з ./V можливих і для кожної з них визначити всі перестанов­ ки. Нагадаємо формулу для обчислення кількості розміщень:

Так само як і для перестановок, можна обґрунтувати корект­ ність формули для обчислення кількості можливих розміщень. Будемо міркувати так: для розміщення першого елемента існує N позицій, для другого - (JV - 1), для третього залишається (N - 2) позицій і т. д., а для М-го елемента - (N - М) позицій. Тому обчислити кількість розміщень можна за допомогою та­ кого добутку: N * (N - 1) * (N - 2) * ... * (N - М + 1). Спростив­ ши наведену вище формулу, отримаємо:

< = VvT^r7: = N*(N-l)*(N-2)*...*(N-M + l). (N-M)l

Хоча на перший погляд останній запис виглядає громіздкі­ шим, однак щодо кількості виконуваних операцій для обчис­ лення А^ він набагато ефективніший.

Якщо використати процедуру для організації вибірки М еле­ ментів з N заданих з назвою регта та процедуру визначення всіх перестановок для цих вибраних елементів з назвою permit, то можна запропонувати такий фрагмент основної програми, який визначатиме всі можливі розміщення:

write(f_ouU[j], " ) ; inc(j);

end; writeln(f_out);

fori := 1 to f 1 — 1 do {Організація всіх перестановок вибраних елементів у масиві t.} begin

perm_t; {Одержання наступної перестановки елементів масиву t.} for j := 1 to m do {Виведення поточної перестановки елементів масиву f.}

write(f_out, t[j], " ) ; writeln(fout);

end;

end;