DataLife Engine > Версия для печати > Генерація комбінаторних об'єктів

Міністерство освіти Республіки Білорусь

Установа навчання

В«Гомельський державний університет ім. Ф. Скорини В»

Математичний факультет

Кафедра МПМ

Реферат

Генерація комбінаторних об'єктів

Виконавець:

Студентка групи М-43

Самусенко А.Ю.

Науковий керівник:

Канд. фіз-мат. наук, доцент

Лебедєва М.Т.

Гомель 2007

Зміст

1 Безліч всіх підмножин ................................................. ..................... 4

2 7

3 11

4 14

5 Перестановки з повтореннями ................................................. ................... 17

6 Сполучення з повтореннями ........................................... .............................. 20

Введення

Існує набір завдань, вирішення яких полягає в генерації всіх елементів таких комбінаторних об'єктів як безліч всіх підмножин, перестановки, поєднання, розміщення, перестановки з повтореннями, поєднання з повтореннями.

Для кожного згенерованого елемента потім перевіряються якісь властивості для конкретного завдання.

Надалі в даній роботі пропонується наступний порядок викладу матеріалу для кожного комбінаторного об'єкту: приклад, алгоритм, програма, коментарі до програми.

1 Безліч всіх підмножин

Нехай ми маємо безліч з 4-х компонент - які ми позначаємо латинськими літерами A, B, C, D відповідно.

І нехай за умовами задачі потрібно вибрати підмножина, що складається з декількох компонент, що володіє деяким властивістю. Пропонується такий спосіб вирішення завдання: ми генеруємо ВСЕ можливі підмножини даної множини і для кожного з згенерованих підмножин перевіряємо задовольняє воно заданими властивостями. Альтернативний варіант завдання - підрахувати ВСЕ підмножини даної множини, що володіють заданою властивістю.

Наприклад:

Для безлічі з 4-х символів A, B, C, D безліч всіх підмножин включає в себе наступні множини:

Пусте безліч

Одноелементні безлічі: {A}, {B}, {C}, {D}

Двоелементні безлічі: {A, B}, {A, C}, {A, D} {B, C}, {B, D}, {C, D}

Трьохелементні безлічі: {A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}

чотириелементних безліч: {A, B, C, D}

У разі, якщо порядок генерації підмножин не грає ролі (а, наприклад, у разі потреби підрахувати всі підмножини, володіють заданою властивістю, так воно і є) один з найбільш просто кодованих алгоритмів генерації безлічі всіх підмножин виглядає наступним чином.

Заведемо вектор B, що складається з чотирьох чисел, кожне з яких може приймати значення 0 або 1. І будемо вважати, що значення 1 вказує на те, що відповідний за номером компонент вихідного безлічі включається до безліч, а значення 0 вказує на те, що елемент не включається.

Розглянемо тепер послідовність двійкових чисел від 0 до 15 і відповідні їм підмножини:

4321

DCBA

0000 - Пусте безліч

0001 A

0010 B

0011 AB

0100 C

0101 AC

0110 BC

0111 ABC

1000 D

1001 AD

1010 BD

1011 ABD

1100 CD

1101 ACD

1110 BCD

1111 ABCD

Таким чином, всього є 16 різних підмножин безлічі з 4-х елементів. У загальному випадку безліч всіх підмножин множини з N елементів містить 2N (два у степені N) елементів.

Алгоритм, що забезпечує таку генерацію безлічі всіх підмножин з N елементів, може бути неформально описаний таким чином:

Формуємо масив, що складається з N нулів - і розглядаємо його як порожній безліч. Таким чином, початкове значення поточного підмножини - порожній безліч.

Для отримання наступного підмножини з поточного підмножини обробляємо поточний масив з чисел 0 або 1 таким чином:

Праворуч (від першого елемента масиву до останнього) шукаємо перше число, рівне нулю.

Якщо таке число не знайдено - значить, поточне підмножина є останнім - безліччю, що складається з усіх елементів, і на цьому алгоритм закінчує свою роботу.

Якщо ж елемент рівний 0 знайдений, то він замінюється на 1, а всі числа праворуч від нього (якщо такі є) замінюються на нулі.

Більше формалізовано цей алгоритм може бути записаний наступним чином:

Введення (N)

Обнулення масиву B з N +1 елемента

Висновок (Пусте безліч)

Поки B [N +1] = 0

i = 1

Поки B [i] = 1 робити B [i] = 0, i = i +1

B [i] = 1

Висновок (безлічі, що визначається масивом B)

Нижче наводиться текст програми, яка зчитує N - число елементів у множині і виводить на екран безліч всіх підмножин позначаючи елементи відповідними по порядку латинськими літерами:

const

<...p> alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b: array [1 .. 100] of byte;

N, i: byte;

begin

readln (N);

for i: = 1 to N +1 do b [i]: = 0;

writeln ('Порожнє безліч');

while (b [N +1] = 0) do

begin

i: = 1;

while B [i] = 1 do

begin B [i]: = 0; inc (i); end;

B [i]: = 1;

for i: = 1 to n do

if b [i] = 1 then write (alphabet [i]);

writeln;

end;

end.

При необхідності обробляти (аналізувати) побудовані підмножини можуть бути додані виклики процедур обробки, які отримують в якості параметра масив B (який вказує своїми одиничними елементами номери елементів безлічі, включених до поточне підмножина).

2 Перестановки

Нехай ми маємо 4 компоненти, позначені літерами A, B, C, D відповідно. p> Тоді безліч всіх перестановок з цих компонент буде включати наступні елементи:

ABCD BACD CABD DABC

ABDC BADC CADB DACB

ACBD BCAD CBAD DBAC

ACDB BCDA CBDA DBCA

ADBC вЂ‹вЂ‹BDAC CDAB DCAB

ADCB BDCA CDBA DCBA

Проілюструємо спочатку алгоритм побудови наступній перестановки на прикладі перестановок з 9 компонент, позначених відповідно цифрами від 1 до 9.

Перша з таких перестановок це

1 2 3 4 5 6 7 8 9

Нехай поточна перестановка з 9 компонент:

1 9 5 8 4 7 6 3 2

Яким буде наступне значення перестановки, якщо ми будуємо її в лексикографічному порядку (тобто в порядку зростання величини числа, складеного з цих цифр)?

Правильна відповідь такий:

1 9 5 8 6 2 3 4 7

Як він виходить?

Перш за все, необхідно переглядати вихідний масив від кінця до початку, що б знайти перше число, яке МЕНШЕ попереднього в нашому випадку - це 4

(7> 6> 3> 2, а 4 <7)

Далі серед переглянутих чисел праворуч від знайденої 4 ми шукаємо останнє число яке більше 4. Це число 6. p> (7> 4, 6> 4, 3 <4, 2 <4)

Потім міняємо ці 2 знайдених числа (4 і 6) місцями, отримуємо:

1 9 5 8 6 7 4 3 2

І тепер числа (праворуч від 6), які складають убуваючу послідовність (4 Липень 3 лютого), попарно міняємо місцями так, що б вони склали зростаючу послідовність (2 березня 7 квітня):

1 9 5 8 6 2 3 4 7

Це і є наступна перестановка.

А яка перестановка буде останньою для даного прикладу?

Сподіваюся, що вдумливий читач здогадався і сам:

9 8 7 6 5 4 3 2 1

Кілька неформально алгоритм побудови наступній перестановки за поточною може бути записаний таким чином:

1. Від кінця до початку перестановки шукаємо перший елемент B [i] такий, що B [i]

2. Від елемента I +1 до кінця шукаємо останній елемент, більший ніж B [i], запам'ятовуємо його індекс - K

3. Міняємо місцями ці елементи - з номерами I і K

4. Всю групу елементів від i +1- го елемента до N-го попарно міняємо місцями (i +1- ий елемент з N-им, i +2- ой елемент з N-1-им і т.д.)

Формалізовано алгоритм генерації всіх перестановок з N елементів може бути записаний таким чином:

Введення N

Прописуємо масив B послідовно числами від 1 до N

Це перша - початкова - перестановка, виводимо її

Поки (істина)

i = N

Поки (i> 0) і (B [i]> = B [i +1]), i = i-1

Якщо i = 0 то кінець роботи

Для j від i +1 до N

якщо B [j]> B [i] то K = j

Обмін значень B [i] і B [k]

Для j від i +1 до (i + ((N +1- i) div 2))

Обмін значень B [j] і B [N + i +1- j]

Висновок поточної перестановки B

Зрозуміло, що цикл попарних перестановок "Хвоста" масиву B не можна робити від i +1 до N-го елемента - інакше елементи поміняються місцями по 2 рази - і вийти, що нічого не змінилося. Цикл потрібно виконати для половини цього "хвоста". Цьому і служить кілька складне для розуміння значення кінцевої змінної циклу: i + (N +1- i) div 2

Нижче наводиться програма, генеруюча всі перестановки з N компонент, позначених N першими літерами латинського алфавіту. p> const

alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b: array [1 .. 100] of byte;

N, i, j, k: byte;

Procedure SwapB (i, k: byte);

var x: byte;

begin

x: = B [i]; B [i]: = B [k]; B [k]: = x;

end;

Procedure WriteB;

begin

for i: = 1 to N do write ({alphabet [b [i]]);

writeln;

end;

begin

readln (N);

for i: = 1 to N do b [i]: = i;

WriteB;

while (true) do

begin

i: = N;

while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;

if i = 0 then exit;

for j: = i +1 to N do

if (B [j]> B [i]) then K: = j;

SwapB (i, k);

for j: ...= i +1 to (i + ((N +1- i) div 2))

do SwapB (j, N + i +1- j);

writeB;

end;

end.

У програмі введені 2 процедури WriteB і SwapB.

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

Процедура SwapB (i, k) введена для спрощення розуміння головної програми. SwapB просто обмінює значеннями два елементи масиву B - ті, які мають індекси, відповідні значенням параметрів процедури i і k.

Процедура SwapB використовується в тексті програми два рази

1) При обміні значеннями двох знайдених елементів з індексами I і K.

2) При забезпеченні попарного обміну елементів "Хвоста", в якому поточний елемент з індексом j обмінюється місцями зі своїм "партнером", що знаходиться на позиції N + i +1- j. Таким чином, I +1- ий елемент поміняється (при J = I +1) місцями з N-м елементом, I +2- ой елемент (При J = I +2) з N-1-им і т.д.

Загальне число перестановок з N елементів одно N! (Читається N факторіал). Нагадаємо, що N! = 1 * 2 * 3 * ... * N

3 Сполучення

Нехай маємо 5 компонент, позначених латинськими літерами A, B, C, D, E відповідно. p> Тоді всі поєднання з цих 5 компонент по 3, виписані у лексикографічному порядку (для букв і цифр від 1 до 5) будуть такі:

ABC 123

ABD 124

ABE 125

ACD 134

ACE 135

ADE 145

BCD 234

BCE 235

BDE 245

CDE 345

Неформально алгоритм генерації послідовності чисел в лексикографічному порядку можна записати наступним чином. Виберемо найменші M з наявних N чисел і випишемо їх у порядку зростання - і випишемо їх у порядку зростання - 1 2 3 - це початкове поєднання. Очевидно, що найбільші M чисел з наявних (3 4 5), виписані у порядку зростання, складуть останнє поєднання.

Для того, що б з поточного поєднанню отримувати наступне, можна поступати таким чином:

Знаходимо позицію в поточному поєднанні, на якій не варто Останнім з можливих значень, і потім збільшуємо його на 1. А все наступні елементи поєднання отримуємо збільшенням на 1 попереднього елемента поєднання.

Наприклад нехай поточне поєднання

1 5 березня

Аналіз починаємо з останньої позиції поєднання.

5 - це останнє можливе значення, тому переходимо до попередньої позиції. 3 - це не останнє можливе значення для цієї позиції (Яким є 4 в даному випадку). Тому ми його збільшуємо на 1 - отримуємо 4. А число в такій позиції отримуємо додатком 1 до цієї 4-ці - і отримуємо 5. Таким чином таке значення буде 1 5 квітня

Більше формалізовано цей алгоритм може бути записаний наступним чином:

Введення N, M (з сколька, по скільки)

Заносимо в масив B числа від 1 до M

Це перше поєднання, виводимо його

Поки (істина)

i = M

Поки (i> 0) і (B [i] = N-m + i), i = i-1

Якщо i = 0 то робота завершена

B [i] = B [i] +1

Для j від i +1 до M B [j] = B [j-1] +1;

Висновок B - наступної перестановки

Нижче наводиться програма, яка зчитує з клавіатури значення N і M і виводить у лексикографічному порядку всі сполучення з N перших латинських букв по M.

uses crt;

const

alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b: array [1 .. 100] of byte;

N, M, i, j, k: byte;

Procedure WriteB;

begin

for i: = 1 to M do write (alphabet [b [i]]);

writeln;

end;

begin

readln (N, M);

for i: = 1 to M do b [i]: = i;

WriteB;

while (true) do

begin

i: = M;

while (i> 0) and (b [i] = N-m + i) do Dec (i);

if i = 0 then exit;

Inc (B [i]);

for j: = i +1 to M do B [j]: = B [j-1] +1;

WriteB;

end;

end.

Нагадаємо, що загальна кількість сполучень з N елементів по M може бути обчислено за формулою C (N, M) = N! /(M! * (N-M)!) br/>
4 Розміщення

Для генерації всіх розміщень з N елементів по M можна скористатися композицією алгоритмів, викладених вище. Тобто генерувати всі поєднання з N по M, а потім для кожного отриманого поєднання генерувати всі перестановки з M елементів.

Наприклад, при генерації всіх розміщень з 5 елементів по 3, у випадку, якщо самі елементи позначені латинськими літерами A, B, C, D, E потрібно отримати наступну послідовність, представлену для компактності у вигляді 10 рядків, кожна з яких представляє всі можливі поєднання з 3 літер першого елемента рядки. А самі перші елементи рядків якраз і являють всі можливі поєднання з 5 букв по 3.

ABC ACB BAC BCA CAB CBA

ABD ...

ABE ...

ACD ...

ACE ...

ADE ...

BCD ...

BCE ...

BDE ...

CDE CED DCE DE...C ECD EDC

Загальна кількість pазмещения - з N елементів по M може бути

знайдено за формулою:

N! /(N-M)! br/>
Нижче наводиться програма, яка вводить з клавіатури числа N, M і генерує всі можливі розміщення з N літер за M.

const

alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

type

barray = array [1 .. 100] of byte;

var

b: barray;

N, M, i, j, k: byte;

z: longint;

Procedure WriteB (B: barray);

begin

Inc (Z); Write (Z: 3, ':');

for i: = 1 to M do write (alphabet [b [i]]);

writeln;

end;

Procedure SwapB (var B: barray; i, k: byte);

var x: byte;

begin

x: = B [i]; B [i]: = B [k]; B [k]: = x;

end;

Procedure PermuteAll (B: barray; N: byte);

var i, k, j: byte;

begin

WriteB (B);

while (true) do

begin

i: = N;

while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;

if i = 0 then exit;

for j: = i +1 to N do

if (B [j]> B [i]) then K: = j;

SwapB (B, i, k);

for j: = i +1 to (i + ((N +1- i) div 2)) do SwapB (B, j, N + i +1- j);

WriteB (B);

end;

end;

begin

readln (N, M);

for i: = 1 to M do b [i]: = i;

PermuteAll (B, M);

while (true) do

begin

i: = M;

while (i> 0) and (b [i] = N-m + i) do Dec (i);

if i = 0 then exit;

Inc (B [i]);

for j: = i +1 to M do B [j]: = B [j-1] +1;

PermuteAll (B, M);

end;

readln;

end.

Пояснення до програми:

1. Головна програма вводить числа N, M і генерує за описаним вище алгоритму всі поєднання з N по M. Для кожного побудованого у векторі B поєднання викликається процедура PermuteAll, якій в якості параметрів передаються поточне поєднання B і кількість елементів у ньому M. Процедура PermuteAll генерує для отриманого поєднання всі можливі перестановки. p> 2. Масив B передається в процедуру PermuteAll за значенням (При оголошенні процедури при параметрі B немає ключового слова VAR) і тому зміни масиву B у процедурі PermuteAll не впливають на вміст масиву B у головній програмі.

3. У той же час для того, що б процедура SwapB могла обмінювати значення в B і повертати змінений масив в зухвалу її процедуру PermuteAll, масив B доданий в параметри процедури SwapB з передачею за адресою - використовуючи ключове слово VAR.

4. Для передачі масиву як параметр заведений спеціальний тип BARRAY.

5. Для підрахунку всіх згенерованих розміщень використовується змінна Z у процедурі WriteB.

5 Перестановки з повтореннями

Перестановки з повтореннями допускають повторне використання елементів. Наприклад, нехай маємо безліч, що складається з двох символів A та двох символів B.

Тоді всі перестановки з повтореннями з цих символів будуть такі:

AABB ABBA BABA ABAB BAAB BBAA

У загальному випадку, якщо маємо

N1 предметів 1-го виду

N2 предметів 2-го виду

...

Nk предметів K-го виду

Загальна кількість перестановок може бути обчислено за формулою

N!/(N1! * N2! * .. * Nk!)

Алгоритм аналогічний генерації перестановок без повторень за винятком формування початкової перестановки:

i = 0;

Для j від 1 до k

Для m від 1 до N [j] i = i +1; B [i] = j;

Нижче наводиться програма генерації перестановок з поверненнями. Кількість K різних типів предметів, позначених латинськими літерами вводиться з клавіатури. З клавіатури також вводяться кількості NN [j] предметів кожного типу.

Сума введених NN [j] визначає загальну кількість елементів у кожній з генеруються перестановок.

const

alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b: array [1 .. 100] of byte;

N, i, j, k, m: byte;

NN: array [1 .. 100] of longint;

Procedure SwapB (i, k: byte);

var x: byte;

begin

x: = B [i]; B [i]: = B [k]; B [k]: = x;

end;

Procedure WriteB;

begin

for i: = 1 to N do write (alphabet [b [i]]);

writeln;

end;

begin

readln (K);

N: = 0;

for i: = 1 to K do

begin read (NN [i]); N: = N + NN [i]; end;

i: = 0;

for j: = 1 to k do

for m: = 1 to NN [j]

do begin Inc (i); B [i]: = j; end;

WriteB;

while (true) do

begin

i: = N;

while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;

if i = 0 then exit;

for j: = i +1 to N do if (B [j]> B [i]) then K: = j;

SwapB (i, k);

for j: = i +1 to (i + ((N +1- i) div 2)) do SwapB (j, N + i +1- j);

WriteB;

end;...

end.
В
6 Сполучення з повтореннями

Для безлічі символів від A до C і розміру M = 3 поєднання з повтореннями будуть наступними:

CCC BCC BBC BBB ACC ABC ABB AAC AAB AAA

Загальна кількість поєднань = (N + M-1)! /(M! * (N-1)!) p> де N - кількість символів

M - по скільки символів в поєднанні

Основна ідея генерації таких сполучень з повтореннями полягає в наступному:

Сполучення записуємо у вигляді (N-1)-го нуля і M одиниць, де одиниці замінюють символи, а нулі виступають в ролі pазделітелей.

Напpимеp:

ABB - 1 0 1 1 AAC - 1 1 0 0 1 CCC - 0 0 1 1 січня

A B B A A C C C C

При такому підході для вирішення завдання досить згенерувати всі перестановки з M одиниць і N-1-го нуля.

Нижче наводиться програма, яка вирішує поставлену задачу.

const

alphabet: string [26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var

b: array [1 .. 100] of byte;

N, i, j, k, M, N1: byte;

Procedure SwapB (i, k: byte);

var x: byte;

begin

x: = B [i]; B [i]: = B [k]; B [k]: = x;

end;

Procedure WriteB;

var i, j: byte;

begin

j: = 1;

for i: = 1 to N do

if b [i] = 0

then Inc (j)

else write (alphabet [j]);

writeln;

end;

begin

readln (N1, M); N: = N1-1 + M;

for i: = 1 to n1-1 do b [i]: = 0;

for i: = n1 to n1 + m-1 do b [i]: = 1;

WriteB;

while (true) do

begin

i: = N;

while (i> 0) and (B [i]> = B [i +1]) do i: = i-1;

if i = 0 then exit;

for j: = i +1 to N do

if (B [j]> B [i]) then K: = j;

SwapB (i, k);

for j: = i +1 to (i + ((N +1- i) div 2)) do

SwapB (j, N + i +1- j);

WriteB;

end;

end.

Пояснення до програми:

1. Початкова перестановка формується послідовно з N1-1 нулів і M одиниць. p> 2. У програмі виведення перестановки WriteB здійснені зміни, відповідні задуму (нулі - роздільники, одиниці - символи). Якщо поточний елемент масиву B дорівнює 0, то "стає активним" наступний символ. Якщо поточний символ масиву B дорівнює 1, то поточний активний символ виводиться на екран.

Висновок

Всі програми для більшої наочності в якості ілюстрації оперують з масивом символів від A до Z. Очевидно, що пропоновані алгоритми та програми практично не змінюються при роботі з масивами елементів будь-якого типу, необхідного за умовами завдання (наприклад, масивами чисел, слів, геометричних фігур і т.д.)

Література

1. Абдеев Р.Ф. Філософія інформаційної цивілізації. - М.: Владос, 1994. p> 2. Адамар Ж. Дослідження психології процесу винаходи в галузі математики. - М.: Сов. радіо, 1970.

3. Болтянский В.Г. Інформатика та викладання математики// Математика в школі. 1989. № 4.-С.86-90

4. Вейценбаум Дж. Можливості обчислювальних машин і людський розум. - М.: Радіо і зв'язок, 1982. p> 5. Вірт Н. Алгоритми + Структури даних = Програма. - М.: Мир, 1989

6. Вірт Н. Систематичне програмування: Введення. - М.: Мир, 1977. p> 7. Громов Г.Р. Нариси інформаційної технології. - М.: ІнфоАрт, 1993. p> 8. Дейкстра Е. Дисципліна програмування. - М.: Мир, 1978. p> 9. Ільєнко Е. В. Філософія і культура. - М.: Політ. літ., 1991.

10. Йодан Е. Структурний проектування і конструювання програм. - М.: Мир, 1979. p> 11. Майерс Г. Надійність програмного забезпечення. - М.: Мир, 1980. p> 12. Махмутов М.І. Організація проблемного навчання в школі. - М., 1986. br/>