Возможные сочетания. Элементы комбинаторики. Перестановки и теория вероятностей

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

Пример

// Сочетания по 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++) - тут можно отметить учебное пособие Т. И. Федоряевой, где приводится алгоритм константной временной сложности для перестановок, да и другие примеры в рунете можно найти, но только для перестановок - а было бы интересно увидеть аналогичные алгоритмы и для других комбинаторных объектов;
  • Нахождение индекса объекта. Тут примеров совсем нет, исключая пособие Федоряевой, причем линейной сложности и только для перестановки;
  • Нахождение объекта по индексу.
Было бы интересно получить справочник по комбинаторным алгоритмам для всех комбинаторных объектов, включая, перестановки, сочетания, размещения, разбиения на подмножества, сочетания с повторениями, размещения с повторениями.

Число сочетаний

Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений .

Явные формулы

Число сочетаний из n по k равно биномиальному коэффициенту

При фиксированном значении n производящей функцией чисел сочетаний с повторениями из n по k является:

Двумерной производящей функцией чисел сочетаний с повторениями является:

Ссылки

  • Р. Стенли Перечислительная комбинаторика. - М.: Мир, 1990.
  • Вычисление числа сочетаний онлайн

Wikimedia Foundation . 2010 .

Смотреть что такое "Число сочетаний" в других словарях:

    70 семьдесят 67 · 68 · 69 · 70 · 71 · 72 · 73 40 · 50 · 60 · 70 · 80 · 90 · 100 Факторизация: 2×5×7 Римская запись: LXX Двоичное: 100 0110 … Википедия

    Световое число, условное число, однозначно выражающее внеш. условия при фотосъёмке (обычно яркость объекта съёмки и светочувствительность применяемого фотоматериала). Любому значению Э. ч. можно подобрать неск. сочетаний диафрагменное число… … Большой энциклопедический политехнический словарь

    Форма числа, выделяющая два предмета как по отношению к единичному предмету, так и по отношению к множеству предметов. В современном русском языке эта форма не существует, но остатки ее влияния сохранились. Так, сочетания два стола (ср. мн. ч.… … Словарь лингвистических терминов

    Комбинаторная математика, комбинаторика, раздел математики, посвященный решению задач выбора и расположения элементов нек рого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения… … Математическая энциклопедия

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

    Занимается изучением событий, наступление которых достоверно неизвестно. Она позволяет судить о разумности ожидания наступления одних событий по сравнению с другими, хотя приписывание численных значений вероятностям событий часто бывает излишним… … Энциклопедия Кольера

    1) то же, что математический Комбинаторный анализ. 2) Раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества объектов… … Большая советская энциклопедия

    - (греч. paradoxos неожиданный, странный) в широком смысле: утверждение, резко расходящееся с общепринятым, устоявшимся мнением, отрицание того, что представляется «безусловно правильным»; в более узком смысле два противоположных утверждения, для… … Философская энциклопедия

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

    Математическая теория, занимающаяся определением числа различных способов распределения данных предметов в известном порядке; имеет особенно важное значение в теории уравнений и в теории вероятностей. Простейшие задачи этого рода заключаются в… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

Книги

  • Учебник английского языка. В двух частях. Часть 2 , Н. А. Бонк, Г. А. Котий, Н. А. Лукьянова. Книга представляет собой вторую часть "Учебника английского языка" . Состоит из 20 уроков, поурочного грамматического справочника и справочных грамматических таблиц. Объем нового лексического…

Все N элементов, и ни один не повторяется, то это задача о количестве перестановок. Решение можно найти простым . На первом месте в ряду может стоять любой из N элементов, следовательно, получается N вариантов. На втором месте - любой, кроме того, который уже был использован для первого места. Следовательно, для каждого из N уже найденных вариантов есть (N - 1) вариантов второго места, и общее количество комбинаций становится N*(N - 1).
Это же можно повторить для остальных элементов ряда. Для самого последнего места остается только один вариант - последний оставшийся элемент. Для предпоследнего - два варианта, и так далее.
Следовательно, для ряда из N неповторяющихся элементов возможных перестановок равно произведению всех целых от 1 до N. Это произведение называется факториалом числа N и обозначается N! (читается «эн факториал»).

В предыдущем случае количество возможных элементов и количество мест ряда совпадали, и их число было равно N. Но возможна ситуация, когда в ряду меньше мест, чем имеется возможных элементов. Иными словами, количество элементов в выборке равно некоторому числу M, причем M < N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Во-первых, может потребоваться сосчитать общее количество возможных способов, которыми можно выстроить в ряд M элементов из N. Такие способы называются размещениями.
Во-вторых, исследователя может интересовать число способов, которыми можно выбрать M элементов из N. При этом порядок расположения элементов уже не важен, но любые два варианта должны различаться между собой хотя бы одним элементом. Такие способы называются сочетаниями.

Чтобы найти количество размещений по M элементов из N, можно прибегнуть к такому же способу рассуждений, как и в случае с перестановками. На первом месте здесь по-прежнему может стоять N элементов, на втором (N - 1), и так далее. Но для последнего места количество возможных вариантов равняется не единице, а (N - M + 1), поскольку, когда размещение будет закончено, останется еще (N - M) неиспользованных элементов.
Таким образом, число размещений по M элементов из N равняется произведению всех целых чисел от (N - M + 1) до N, или, что то же самое, частному N!/(N - M)!.

Очевидно, что количество сочетаний по M элементов из N будет меньше количества размещений. Для каждого возможного сочетания есть M! возможных размещений, зависящих от порядка элементов этого сочетания. Следовательно, чтобы найти это количество, нужно разделить число размещений по M элементов из N на N!. Иными словами, количество сочетаний по M элементов из N равно N!/(M!*(N - M)!).

КАТЕГОРИИ

ПОПУЛЯРНЫЕ СТАТЬИ

© 2024 «unistomlg.ru» — Портал готовых домашних заданий