Комбинаторные алгоритмы применяются достаточно часто. В интернете можно найти много информации касательно комбинаторных алгоритмов. Однако русскоязычный интернет, в основном, выдает простейшие задачи сплошного перебора (генерации) комбинаторных объектов в цикле. Например:

Пример

// Сочетания по 3 из 52 for (int i1 = 0; i1 < 50; ++i1) for (int i2 = i1+1; i2 < 51; ++i2) for (int i3 = i2+1; i3 < 52; ++i3) // ...

Индекс сочетания

Каждому сочетанию, перестановке, размещению и другим комбинаторным объектам можно сопоставить индекс - это номер, в котором он появляется при переборе данным алгоритмом.

Здесь мы рассмотрим более сложную задачу, решения которой в рунете я не нашел (впрочем, приведу одну ссылку , но та формула явно неверная) - исходя из самого сочетания (в данном случае набора трех чисел) найти его индекс.

Есть вариант перебора «в лоб». Включаем счетчик сочетаний, берем алгоритм выше и пока не дойдем до нужного варианта перебираем все подряд. Такой вариант имеет очень большую временную сложность, поэтому такой вариант отбросим.
Положим, на входе имеются числа i1, i2, i3. Нам, прежде всего, нужно их упорядочить в порядке возрастания (обратите внимание, что сам алгоритм генерации, приведенный выше, выдает их всегда в упорядоченном виде, хотя само понятие «сочетание» подразумевает произвольный порядок).

Положим, для определенности, после упорядочивания i1 = 3, i2 = 7, i3 = 12.
Это значит, мы «прошли» все сочетания, где i1 было равным 0, 1 и 2.
Для i1 = 0 мы прошли C(2, 51) сочетаний, поскольку индексы i1, i2 пробегают все сочетания по 2 из 51 числа.
Для i1 = 1 мы прошли C(2, 50) сочетаний.
Для i1 = 2 мы прошли C(2, 49) сочетаний.
Итого мы прошли СУММА {от n = 0 по n = i1-1) C(2, 51-n}.
При i1 = 3 рассмотрим уже те сочетания, которые мы прошли, бегая по индексу i2 (а он у нас начинается с i2 = i1+1 = 4).
При i2 = 4 прошли C(1, 47) сочетаний, при i2 = 5 прошли C(1, 46) сочетаний, при i2 = 6 прошли C(1, 45) сочетаний.
По полной аналогии, при i2 = 7 рассматриваем сочетания, которые пробежал индекс i3.
Получаем общую формулу:
Искомый индекс сочетания = СУММА {от n = 0 по i1-1} C(2, 51-n) + СУММА {от n = i1+1 по i2-1} C(1, 51-n) + СУММА {от n = i2+1 по i3-1} C (0, 51-n).

Индекс разбиения на подмножества

В комбинаторике есть и более сложный объект - разбиение на подмножества. К примеру, разбиение 52-элементного множества на три подмножества, состоящие соответственно, скажем, из 2, 3 и 47 элементов, где порядок элементов внутри каждого подмножества неважен. (Кстати сказать, сочетание по 2 из 52 - это просто частный случай разбиения на два подмножества из 2 и 50 элементов соответственно).

Типовой алгоритм генерации заключается в том, что мы генерируем сочетания по 2 из 52, и для каждого такого сочетания во вложенном цикле генерируем сочетания по 3 из 50, причем проверяем, чтобы индексы (i3, i4, i5) во вложенном сочетании не совпадали с индексами (i1, i2) во внешнем сочетании:

Код на C++

// ВНЕШНЕЕ СОЧЕТАНИЕ for (int i1 = 0; i1 < 51; ++i1) for (int i2 = i1+1; i2 < 52; ++i2) // ВНУТРЕННЕЕ СОЧЕТАНИЕ for (int i3 = 0; i3 < 50; ++i3) if (i3 != i1 && i3 != i2) for (int i4 = i3+1; i4 < 51; ++i4) if (i4 != i1 && i4 != i2) for (int i5 = i4+1; i5 < 52; ++i5) if (i5 != i1 && i5 != i2) // ...

Опять же, каждое такое разбиение имеет свой индекс.
Оказывается, наш алгоритм нахождения индекса сочетания можно модифицировать для нахождения индекса разбиения.
Надо обратить внимание, что индексы во «внешнем сочетании» i1, i2 нам нужно упорядочивать между собой, а индексы i3, i4, i5 - между собой, но независимо от первых двух.
Также следует учесть, что во «вложенном сочетании» по сути мы работаем с 50-элементным множеством, но индексы i3, i4, i5 нужно определенным образом «сдвинуть», чтобы они менялись не от 0 до 51, а от 0 до 49:

Код на C++

if (i3 >= i1) --i3; if (i3 >= i2) --i2; // аналогично для i4, i5

(так сказать, мы вырезаем из нашего 52-элементного множества индексы i1, i2 и потом сдвигаем оставшееся множество, чтобы закрыть дырки, при этом сдвигаются индексы i3-i5).
Следует учесть при этом, что внутри каждого «внешнего» сочетания у нас сидит ровно C(3, 50) «вложенных» сочетаний.
Тогда алгоритм сведется к следующему:
ИНДЕКС_СОЧЕТАНИЯ (i1, i2 из 52) * ЧИСЛО_СОЧЕТАНИЙ_ПО_3_ИЗ_50 + ИНДЕКС_СОЧЕТАНИЯ (i3, i4, i5 из 50 после сдвига индексов).

Приведение алгоритмов к константной сложности

Сразу должен обратить внимание, что в формуле возникает «ошибка», если например, i1 = 0 (мы считаем сумму для n = от 0 до -1) или i2 = 1 (считаем сумму от 1 до 0). На самом деле в таких случаях соответствующую сумму следует принимать равной нулю, и результат получится корректным.
Также должен обратить внимание на временнУю сложность наших алгоритмов: они имеют линейную сложность при условии, что C вы считаете за константное время. Это уже намного лучше, чем перебор «в лоб».
Но на самом деле (в нашем случае 52) ничего не мешает свести алгоритм к константной сложности. Для этого применим знания математики и аналитически посчитаем все суммы.
Например, число сочетаний C(2, K), если «раскрыть» его в виде формулы K! / ((K-2)! * 2!), приводится к многочлену 2-й степени. А поскольку он у нас под знаком суммы, то можно применить формулы суммы N-х степеней чисел натурального ряда (см. Википедию) и получить один-единственный многочлен 3-й степени. Который, очевидно, имеет константную временную сложность. (Причем «ошибка», которую я привел в начале подзаголовка, никак себя не проявляет, формула остается корректной).
Повторюсь, это для фиксированной размерности базового множества . Впрочем, уверен, с помощью метапрограммирования можно «научить» компилятор, чтобы он делал эту работу за вас.

Пример кода для индекса разбиения на 2, 3, 47

int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) { // Индекс сочетания по 2 из 52, умноженный на C(3, 50) int offset = ((52*51 - (51-i1)*(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // "Переиндексируем" внутреннюю группу так, чтобы была нумерация 0...49 if (i3 >= i1) --i3; if (i3 >= i2) --i3; if (i4 >= i1) --i4; if (i4 >= i2) --i4; if (i5 >= i1) --i5; if (i5 >= i2) --i5; // Теперь прибавим индекс сочетания по 3 // 0: // СУММА для n = 0 по i3-1 СОЧЕТАНИЙ (2, 49-n) // = СУММА для m = 50-i3 по 49 (m * (m-1) / 2) offset += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3)) / 2) / 2); // 1: // СУММА для n = i3+1 по i4-1 СОЧЕТАНИЙ (1, 49-n) offset += (((48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // СУММА для n = i4+1 по i5-1 (1) offset += (i5 - i4 - 1); return offset; }

Послесловие

Мне в своем симуляторе покера (Texas Hold"em) захотелось заранее рассчитать и хранить вероятности выигрыша для всех возможных сочетаний из моих ручных карт (2 штуки) и всех карт флопа (3 карты на столе). Это соответствует разбиению 52-множества на 2, 3, 47 подмножества.
Рассчитал и сохранил.
Но когда пришло время прочитать данные из файла для конкретной комбинации, уж очень мне не хотелось что-то там долго вычислять или производить поиск в гигабайтном файле. Теперь я просто определяю смещение в файле и считываю непосредственно то, что мне надо.

Вообще, комбинаторные алгоритмы я бы разбил на такие классы:

• Генерация комбинаторных объектов в едином цикле (тут все просто, примеры я привел);
• Переход к следующему (или предыдущему) комбинаторному объекту, зная предыдущий (своего рода forward/backward iterator, выражаясь в терминах C++) - тут можно отметить учебное пособие Т. И. Федоряевой, где приводится алгоритм константной временной сложности для перестановок, да и другие примеры в рунете можно найти, но только для перестановок - а было бы интересно увидеть аналогичные алгоритмы и для других комбинаторных объектов;
• Нахождение индекса объекта. Тут примеров совсем нет, исключая пособие Федоряевой, причем линейной сложности и только для перестановки;
• Нахождение объекта по индексу.

Было бы интересно получить справочник по комбинаторным алгоритмам для всех комбинаторных объектов, включая, перестановки, сочетания, размещения, разбиения на подмножества, сочетания с повторениями, размещения с повторениями.

Приближалась зима, и Хома с Сусликом решили запастись горохом. Весь день они бегали в амбар и таскали по несколько стручков: Хома по четыре, а Суслик по два. К вечеру они пересчитали все стручки, что они натаскали, и задумались, как теперь этот горох делить. Хома утверждал, что если он за раз тащил в два раза больше, чем Суслик, то и гороха ему должно достаться в два раза больше. Суслик на это резонно возражал, что, во-первых, скорость у Хомы заметно меньше, чем у Суслика, а, во-вторых, кто его знает, может Хома всего раз-два сбегал, а остальное время бездельничал…

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

Входные данные

В первой строке натуральное четное число M – количество украденных стручков, 2 ≤ M ≤ 1000.

Выходные данные

Все возможные сочетания количеств стручков, принесенных Сусликом и Хомой по одному сочетанию в строке. Каждое сочетание представляет собой два целых неотрицательных числа через пробел: первое число – количество стручков, принесенных Сусликом, второе – принесенных Хомой. Сочетания упорядочить по убыванию первого числа.

Тесты

Входные данные	Выходные данные
6	\\ 6 \; 0 \\ 2 \; 4
11	\\ 11\;0 \\ 7\;4 \\ 3\;8
18	\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16

Код программы

#include using namespace std ; int main () { int a , b = 0 ; cin >> a ; while (a >= 0 ) { cout << a << " " << b << "\n" ; a -= 4 ; b += 4 ; return 0 ;

Решение задачи

Пусть a — количество стручков, принесенных Хомой и b — количество стручков, принесенных Сусликом. Так как по условию задачи Хома таскал только по четыре стручка, мы будем считать a = a-4 и b = b + 4, чтобы таким образом перебрать все возможные сочетания количеств стручков, принесенных Сусликом и Хомой. Также воспользуемся циклом while , который будет повторять действие, описанное выше, до тех пор, пока a \geq 0. В ответе выводим все возможные сочетания количеств стручков, принесенных друзьями по одному в строке, упорядоченные по убыванию первого числа.

Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.

Основная формула комбинаторики

Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *...*n k .

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

Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?
Решение: n 1 =6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.

В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =...n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.

Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8?
Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.

Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .

Число размещений из n элементов по m

Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:

Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.

Пример 5 . Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные?
Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.

Число сочетаний из n элементов по m

Число сочетаний обозначается C n m и вычисляется по формуле:

Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?

Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

Перестановки из n элементов

Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.

Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?

Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.

Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).

Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.

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

Пример 9. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?
Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.

Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок , которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.

Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?

4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?

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

6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество N , состоящее из n элементов. Любое подмножество, состоящее из m элементов можно рассматривать без учета их порядка, так и с его учетом, т.е. при изменении порядка переходим к другой m – выборке.

Сформулируем следующие определения:

Размещения без повторения

Размещением без повторения из n элементов по m N , содержащее m различных элементов .

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

Теорема 3 . Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n . Записывают:

Перестановки без повторений

Перестановками из n элементов называются различные упорядочения множества N .

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

Теорема 4 . Число различных перестановок без повторений вычисляется по формуле

Сочетания без повторений

Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N , содержащее m различных элементов.

Из определения следует, что два сочетания различаются только элементами, порядок не важен.

Теорема 5 . Число сочетаний без повторений вычисляют по одной из следующих формул:

Пример 1 . В комнате 5 стульев. Сколькими способами можно разместить на них

а) 7 человек; б) 5 человек; в) 3 человека?

Решение: а) Прежде всего надо выбрать 5 человек из 7 для посадки на стулья. Это можно сделать
способом. С каждым выбором конкретной пятерки можно произвести
перестановок местами. Согласно теореме умножения искомое число способов посадки равно.

Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как

б) Решение очевидно -

в) - число выборов занимаемых стульев.

- число размещений трех человек на трех выбранных стульях.

Общее число выборов равно .

Не трудно проверить формулы
;

;

Число всех подмножеств множества, состоящего из n элементов.

Размещения с повторением

Размещением с повторением из n элементов по m называется всякое упорядоченное подмножество множества N , состоящее из m элементов так, что любой элемент ожжет входить в это подмножество от 1 до m раз, либо вообще в нем отсутствовать .

Число размещений с повторением обозначают и вычисляют по формуле, представляющей собой следствие из теоремы умножения:

Пример 2 . Пусть дано множество из трех букв N = {a, b, c}. Назовем словом любой набор из букв, входящих в это множество. Найдем количество слов длиной 2, которые можно составить из этих букв:
.

Замечание: Очевидно, размещения с повторением можно рассматривать и при
.

Пример 3 . Требуется из букв {a, b}, составить всевозможные слова длиной 3. Сколькими способами это можно сделать?

Ответ :