Комбинаторные алгоритмы решения школьных задач по информатике

На параметры GetBinomialCoefficient, RandomFunc, n, k, Src, Dest, First, Last, типы RandomAccessIterator, InputIterator, OutputIterator накладываются те же ограничения и требования, что и в функциях, реализующих алгоритм генерации методом случайной перестановки.

Параметр CombNumber (там, где  он присутствует) должен удовлетворять условию 0≤CombNumber≤C(n,k) – это порядковый номер сочетания.

Функции с названием CombinationFromNumberBool() генерируют сочетание по заданному номеру в формате «список из bool». На вход им подаётся номер сочетания, его размер, возможно, функциональный объект, вычисляющий число сочетаний (если его нет, то таковой выбирается по умолчанию). На выходе они должны записать в Dest последовательность элементов, синтаксически совместимых с bool (которым можно присвоить значение типа bool).

Функции с названием CombinationFromNumber() генерируют сочетание по заданному номеру в формате «подмножество». На вход они принимают то же, что и CombinationFromNumberBool(), а также итератор (итераторы), описывающий входную последовательность. На выходе они должны сформировать нужную подпоследовательность (другими словами, сочетание) и записать её в Dest.

Функции с названиями RandomCombinationFromNumberBool() и RandomCombinationFromNumber() генерируют случайные сочетания в форматах «список из bool» и «подмножество», соответственно. На вход имеют те же параметры, что и соответствующие им функции без префикса «Random», за исключением параметра RandomFunc, который передаётся вместо CombNumber. Вызывают соответствующие им функции (без префикса «Random») с параметром CombNumber = RandomFunc(GetBinomialCoefficient(n,k)).

4.2. Сочетания с повторениями

Имеются элементы n различных  типов. Сколько совокупностей, содержащих по k элементов каждая, можно составить  из них, если не принимать во внимание порядок расположения элементов в совокупности? Задачи такого типа называют задачами на сочетания с повторениями.

Определение. Сочетанием с повторениями из данных n различных типов элементов по k элементов называется всякая совокупность, содержащая k элементов, каждый из которых  является одним из элементов указанных типов.

Как видно из определения, сочетания с повторениями являются неупорядоченными множествами, а различные  сочетания отличаются друг от друга  входящими в них элементами, причем каждый элемент может входить  в сочетание несколько раз. Для сочетаний с повторениями возможен случай, когда  n < k. Число различных сочетаний с повторениями из n элементов по k будем обозначать символом   .

Теорема. Число различных сочетаний с повторениями из n типов элементов по k элементов определяется по формуле:

Пример 1.

Пусть в коробке лежат  шары трех цветов—красного, синего и  зеленого. Шары одного цвета считаются  одинаковыми. Вопрос: сколькими способами  можно составить набор из двух шаров?  Легко видеть, что это задача на определение числа сочетаний с повторениями. Пусть “к” означает произвольный красный шар, “c”—синий и “з”—зеленый. Тогда все сочетания с повторениями этих трех сортов по два суть : {с,к}, {с,с}, {с,з}, {з,к}, {з,з}, {к,к}. 
Число сочетаний с повторениями из n элементов по k обозначается ar{C}^k_n и равно C^k_n+k-1

Пример 2.

Обычно, при использовании лототронов после вытягивания из набора очередного "лота" (шарика, фанта, свернутой записки и т.д.), этот лот удаляется из оставшегося набора. Если же его вернуть в исходный набор, тогда мы и получим "сочетание с повторением". Возвращаясь к предыдущей задаче "6 из 49", за счет повторений мы можем получить, например, вариант {5, 8, 21, 24, 24, 35}. Всего возможно   = 25 827 165 вариантов (к 13 983 816 вариантов без повторений добавляются 11 843 349 повторяющихся вариантов).

Пример 3. 

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и картошка. Сколькими способами можно купить 7 пирожных?

Решение. Положим пирожные в коробку, а чтобы они не перепутались, разделим их картонными разделителями. Нужно 3 разделителя. Обозначения: 0 (картонки-разделители) и 1 — пирожные. Примерная покупка: 1110101101 — три наполеона, 1 эклер, 2 песочных и 1 картошка.

Итак, два класса объектов 1 (7 штук) и 0 (3 штуки) — покупка — 10 объектов.

Два способа рассуждения:

(1) задача сводится к выбору мест для 7 пирожных (или для 3 разделителей) среди 10 объектов.

(2) другой способ рассуждения (эквивалентный). Надо разбить 10 мест на две группы: для 7 пирожных и 3 разделителей.

В чем особенность: объекты  повторяются, причем один эклер на вкус неотличим от другого. Отсюда название: сочетания с повторениями. Можно  представлять себе, что пирожные непрерывно пекут, так что они не переводятся, сколько ни ешь. Это совсем другая ситуация, чем в обычных сочетаниях!!!

Пусть заданы два числа:   — число выбираемых элементов, и   — число типов элементов, из которых производится выбор. Число     сочетаний с повторениями из элементов   типов равно числу способов выбора мест для собственно выбираемых элементов различных классов, или, что то же: для разделителей между ними.

Итак, основная формула:

Задача. Имеется   одинаковых предметов. Сколькими способами можно распределить эти предметы между  лицами?

 

 5. Комбинаторные  алгоритмы. Перестановки

5.1. Число перестановок из n элементов

Перестановки - это множества, состоящие из одних и тех же элементов и отличающиеся только порядком расположения этих элементов. Возьмем n различных элементов {a1, a2, a3, . . . , an} и переставим эти элементы всевозможными способами, оставляя без изменения числа элементов, меняя только порядок их расположения. Обозначим общее число полученных таким образом перестановок P_n. Число перестановок вычисляется по следующей формуле:

Наша цель состоит  в том, чтобы построить алгоритм генерации перестановки по заданному  номеру и алгоритм нумерации перестановки. Для этого рассмотрим рис. 5.1, на котором показан фрагмент дерева для получения перестановок множества символов {a, b, c}.

Рис. 5.1. Дерево для получения перестановок множества символов.

Корень этого дерева содержит первый символ «a», при этом слева и справа от этого символа  записаны кружки, которые показывают, где может находиться следующий  символ «b» относительно «a». Выходные дуги из корня показывают варианты перехода (их всего два). Символ «c» для каждого варианта может находиться в трех позициях, отмеченных кружками. Соответственно, из каждой вершины «ba» и «ab» следует по три дуги. Это дает 6 вариантов перестановок. Построение дерева перестановок можно продолжить для 4 элементов. Из каждого узла, содержащего 3 элемента, будет выходить по 4 дуги. Вариантов перестановок будет 24.

Задавая путь в таком  дереве, можно получить некоторую  перестановку. Алгоритм построения перестановки по дереву основан на операциях сдвига и вставки. Берется первый элемент и ставится в позицию 1, берется i-й элемент и определяется его позиция j(0 < j < i). Все элементы, стоящие справа от j-го элемента, сдвигаются на одну позицию вправо, сдвиг начинается с j-го. На место j-го элемента становится данный i-й элемент.

Рассмотрим теперь вопросы  генерации перестановки по ее номеру. Пусть задано множество E = {a1, a2, a3, . . . , an} и некоторое целое число k, удовлетворяющее условию

0 < k <= n!

Необходимо найти k-ю  перестановку. Для того, чтобы найти заданную перестановку, необходимо по числу k найти позицию каждого элемента ai и использовать вышеизложенный алгоритм построения перестановки. Номера позиций вычисляются следующим образом:

Тогда алгоритм генерации k-й перестановки множества E = {a1, a2, a3, . . . , an} будет следующий:

1. i = 1 в элемент массива v[i] = a1;
2. если i > n, конец;
3. вычислить pi = k mod i , k = k/i;
4. выполнить операцию сдвига вправо в массиве v относительно позиции pi ; v[pi] = ai;
5. i = i + 1, перейти на шаг 2.

Назовем этот алгоритм GPermutation.

Ниже приведены функции  для реализации предложенного алгоритма  генерации:

Функция вставки номера в массив перестановки

void Insert(int v[ ], int n, int i, int a) 
{ 
      for (int j=n-2; j>=i; j--) v[j+1]=v[j]; //сдвиг 
      v[i]=a; //вставка 
}

Функция генерации перестановки по заданному номеру

void GeneratePermutation(int v[ ], int n, int k) 
{ 
      int pos; 
      v[0]=1; 
      for (int i=2; i<=n; i++){ 
            pos=k%i; 
            k=k/i; 
            Insert (v,i,pos,i); 
      } 
}

5.2 Определение номера перестановки. Определение перестановки по номеру

 Алгоритм идентификации перестановки

Пусть задана перестановка P, необходимо поставить в соответствие некоторый номер. Этот алгоритм можно построить на основе алгоритма генерации, используя обратный механизм сдвига влево и удаления. Алгоритм идентификации следующий.

Дан массив v[n], в котором  записана перестановка (см. алгоритм GPermutation).

Необходимо найти номер k :

1. i = n, k = 0.
2. Eсли i равно 1, то конец.
3. Ищем в массиве v элемент, содержащий i.
4. Полученный индекс присваиваем j.
5. Вычисляем k = k - (i + 1) + j.
6. Сдвигаем влево на одну позицию в массиве v относительно j.
7. i = i - 1.
8. Переход на шаг 2.

Функция сдвига вектора  перестановки влево в заданной позиции

void ShiftLeft (int v[ ], int n, int pos) 
{ 
      for (int k=pos; k<n; k++){ 
            v[k]=v[k+1]; 
      } 
}

Функция определения номера перестановки

int Num (int v[ ], int n) 
{ 
      int num=0; 
      for (int k=n; k>=1; k--){//начинаем с конца 
            for (int j=0; j<k; j++){//ищем позицию текущего числа 
                  if (v[j]==k){ 
                        num=num*k+j; //производим вычисление 
                        ShiftLeft(v, k, j); 
                  } 
            } 
      } 
      return num; 
}

Пример использования  функций генерации и нумерации  перестановок

//вычисление факториала (количества перестановок) 
int Factorial(int n) 
{ 
      if (n <= 1) return 1; 
      else return n*Factorial(n-1); 
} 
//печать вектора перестановки 
PrintPermut (int v[ ], int n) 
{ 
      for (int i=0; i<n; i++){ 
            printf("%d", v[i]); 
      } 
      printf("\n"); 
} 
#define SIZE 5 
int v[SIZE]; 
void TestPermutation() 
{ 
      int k=Factorial(SIZE); //вычисление количества перестановок 
      printf("permutation(%d) = %d\n", SIZE, k); 
      for (int i=0; i<k; i++){//перечислить все перестановки 
            GeneratePermutation (v, SIZE, k-i-1); //найти i-ю перстановку 
            PrintPermut (v, SIZE); 
            printf("num = %d\n", Num(v, SIZE)); //найти и отпечатать номер данной перестановки 
      } 
      getch(); 
}

5.3. Перестановки с повторениями

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

Всякое размещение с  повторениями, в котором элемент   повторяется   раз, элемент   повторяется   раз и т.д. элемент   повторяется   раз, где  ,  ,  ,   — данные числа, называется перестановкой с повторениями порядка

в которой данные элементы   повторяются соответственно  ,  ,   раз.

Теорема. Число различных перестановок с повторениями из элементов  , в которых элементы   повторяются соответственно   раз, равно

Доказательство. Если мы будем считать все   элементов перестановки с повторениями различными, то всего различных вариантов перестановок   элементов —  . Однако среди этих перестановок не все различны. В самом деле, все элементы   мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы  ,  ,  ,  . Таким образом, всякая перестановка может быть записана  способами. Следовательно, число различных перестановок с повторениями равно

Задача 1. Дано   различных предметов. Сколькими способами можно разбить эти предметы на 3 группы так, чтобы первая группа содержала   предметов, вторая   предметов, а третья   предметов?

Пример. Сколько различных шестизначных чисел можно составить из цифр 1, 1, 1, 5, 5, 9? Подставим в формулу   различных шестизначных чисел.

Задача 2. Сколько различных слов можно получить, переставляя буквы слова "математика"?

 

6. Множества и алгоритмы  перебора

6.1. Подмножество. Перечисление подмножеств

Перечисленные подзадачи  в программировании обычно рассматривают  для следующих комбинаторных конфигураций: перестановки элементов множества, подмножества множества, сочетания из n элементов множества по k элементов (k-элементные подмножества множества, состоящего из n³kэлементов), размещения (упорядоченные подмножества множества, то есть отличающиеся не только составом элементов, но и порядком элементов в них), разбиения множества (множество разбивается на подмножества произвольного размера так, что каждый элемент исходного множества содержится ровно в одном подмножестве), разбиения натуральных чисел на слагаемые, правильные скобочные последовательности (различные правильные взаимные расположения n пар открывающихся и закрывающихся скобок).

Однако при генерации  различных конфигураций использовались в основном нерекурсивные алгоритмы. Опытные же участники олимпиад в подобных случаях при программировании используют в основном именно рекурсию, с помощью которой решение рассматриваемых задач зачастую можно записать более кратко и прозрачно. Поэтому для полноты изложения данной темы приведем ряд рекурсивных комбинаторных алгоритмов и рассмотрим особенности применения рекурсии в комбинаторике.