Генерация сочетаний без повторений

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

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

Задача : Найти все возможные сочетания без повторений из множества элементов <1,2,3>по 2.
Существуют следующие сочетания:

1: 1 2
2: 1 3
3: 2 3

Количество возможных сочетаний без повторений из N элементов по M можно определить по формуле (N≥M):

что в M! раз меньше соответствующего количества размещений без повторений (поскольку сочетания без повторений не зависят от порядка следования элементов).

Рассмотрим задачу получения всех сочетаний для чисел 1…N по M.

Реализация на С++

Результат выполнения

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

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

Примером такой задачи может служить выбор M открыток из N всеми возможными способами.

Для генерации сочетаний с повторениями воспользуемся решением для генерации размещений с повторениями, рассмотренным в этой статье.

Реализация на С++

Результат работы приведенного выше алгоритма:

Эту статью я написал несколько лет назад для другого сайта, но она так и не была опубликована. Тогда 7-я версия Java только-только появилась на свет, а 6-я была всё ещё актуальна. Статья адресована, тем, кто уже имеет некоторый опыт программирования на языке Java и не прочь разобраться в алгоритме генерации сочетаний. Я решил стряхнуть со статьи пыль и опубликовать её: пусть будет!

Здравствуйте, уважаемый читатель! В этой статье мы рассмотрим программу, генерирующую все сочетания из n элементов по m.

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

За круглым столом сидят 12 представителей различных государств, причём каждый из них враждует с соседями справа и слева. Из этих представителей нужно сформировать комиссию, состоящую из 5 человек, причём никакие два члена комиссии не должны враждовать между собой. Каким количеством способов можно сформировать такую комиссию?

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

Тогда одна из комиссий, в которых нет врагов, будет выглядеть так: <1, 3, 5, 7, 9>. На основе этой комиссии можно сформировать ещё одну, если каждого члена заменить его соседом слева: <2, 4, 6, 8, 10>. И ещё такую операцию можно проделать 10 раз. Таким образом, получаем 12 вариантов.

Аналогично: формируем комиссию <1, 4, 7, 9, 11>и получаем на её основе ещё 11 комиссий. Всего 12 вариантов.

Наконец, формируем комиссию <1, 3, 6, 8, 10>и получаем на её основе ещё 11 комиссий. Общее количество комиссий — 12.

Итого: 12 + 12 + 12 = 36 вариантов. Это и есть окончательный ответ.

Я был уверен в правильности ответа, но всё же захотел проверить себя с помощью метода перебора. Для его реализации необходимо перебрать все возможные варианты комиссий из 5 человек и выбрать те из них, которые удовлетворяют условиям задачи. Поскольку вариантов много (а именно, 792, как будет показано далее), я решил прибегнуть к помощи компьютера.

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

Родственным понятием по отношению к сочетанию является размещение. Из n элементов будем теперь формировать всевозможные упорядоченные наборы по m элементов в каждом наборе, где m не превышает n, такие, что все элементы в каждом наборе различны и любые два набора различаются составом или порядком входящих в них элементов. Эти наборы называются размещениями из n элементов по m.

Несложно подсчитать число всех размещений из n элементов по m, обозначаемое как A n m . Один из элементов, входящих в размещение, можно выбрать n возможными способами, второй — (n – 1) возможными способами и т. д. Наконец, последний, m-й элемент, можно выбрать (n–m) возможными способами. Перемножив эти количества способов, получаем искомое число всех размещений: A n m = n ‘ n – 1 ‘ … ‘ n – m + 1 . С использованием факториалов число размещений записывается так: A n m = n ! n – m ! .

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

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

C n m = A n m A m m = n ‘ n – 1 ‘ … ‘ n – m + 1 m ‘ m – 1 · … · 1 = n ! m ! ‘ n – m ! .

Очевидно, теперь, что комиссии — это и есть сочетания из 12 представителей по 5. Можно теперь подсчитать и число всех возможных комиссий. Оно равно 12 ! 5 ! 7 ! = 792 .

Таким образом, задача перебора всех комиссий, состоящих из 5 представителей, эквивалентна задаче перебора всех сочетаний из 12 элементов по 5. Её решением (в общем виде) мы сейчас и займёмся.

Пронумеруем n элементов номерами от 1 до n. Сочетания будем записывать в виде номеров элементов, входящих в эти сочетания, разделённых запятыми и помещённых в фигурные скобки.

Заметим, что порядок элементов в записи сочетания не важен. Например, <1, 2, 3, 4, 5>и <5, 4, 3, 2, 1>— это одно и то же сочетание. А раз порядок не важен, то договоримся записывать элементы в порядке возрастания номеров.

Теперь, в соответствии с описанным способом упорядочивания, все сочетания можно единственным образом выстроить в одну цепочку, начинающуюся с сочетания <1, 2, …, m> и заканчивающуюся сочетанием <n, n – 1, …, n – m + 1>. Именно в таком порядке мы и будем генерировать сочетания.

Составим алгоритм, который по заданному сочетанию создаёт сочетание, непосредственно следующее за ним (разумеется, за исключением случая, когда алгоритму передаётся сочетание, “замыкающее” цепочку; в этом случае алгоритм ничего не возвращает).

1. Полагаем: t = m.
2. Если a_t Combinations . Значения m и n хранятся в статических целочисленных константах M и N соответственно. Сочетание в программе представлено целочисленным массивом из M элементов. В ячейке массива с индексом t хранится номер элемента сочетания с индексом t + 1.

Описанный выше алгоритм реализован в статическом методе generateCombinations() . Метод принимает массив, хранящий сочетание, генерирует по переданному сочетанию новое, помещает его в тот же самый массив и возвращает этот массив.

Если методу передано значение null , то он возвращает массив с первым сочетанием. Если методу передан массив с последним сочетанием, то метод возвращает null .

Управление методом generateCombinations() осуществляется из метода main() . Сначала generateCombinations() вызывается со значением null , затем каждый массив, возвращаемый этим методом, передаётся методу снова, до тех пор, пока метод не вернёт null . Каждый сгенерированный массив преобразуется в строку статическим методом toString() класса java.util.Arrays и выводится на консоль.

Ниже приведён код класса Combinations .

Наша программа генерирует все сочетания из 5 элементов по 3. Запуск класса Combinations на выполнение приведёт к печати следующих результатов:

Как видим, программа работает корректно.

Итак, сочетания генерировать мы научились, вернёмся теперь к нашей задаче. Присвоим константам M и N значения 5 и 12 соответственно, а также изменим тело цикла while в методе main() . На этот раз будем выводить на печать только те сочетания, которым соответствуют комиссии, не содержащие ни одной пары соседей.

Этому критерию удовлетворяют только те сочетания, которые не содержат элементов с номерами, различающимися на единицу, а также не включают в себя элементов с номерами 1 и 12 одновременно.

Вот исходный код новой версии нашей программы:

На этот раз запуск программы приведёт к следующему выводу на консоль:

Как мы видим, число искомых сочетаний действительно равно 36.

В следующей части статьи мы перепишем наши программы в объектно-ориентированном стиле с использованием интерфейсов Iterator и Iterable .

На этом всё. Спасибо за внимание!

Комментарий, сделанный в июне 2016 года. Планируемое в предпоследнем абзаце продолжение статьи так и не было написано. Кто знает — может, я, всё-таки, когда-нибудь и возьмусь за его написание. Почему бы и нет?

Требуется перебрать все комбинации группы символов от A до X где X может быть любой другой буквой.

Пример: дана последовательность ABCD, функция должна выдать AB, AC, AD, BC, BD, CD, ABC, BCD, CDA, ABD (вроде ничего не забыл), т.е. позиция символа в группе не важна – важна лишь уникальность самой группы.

Гуглил в сторону размещений и сочетаний. Но так и не понял что именно из этого мне требуется. Грешен – не учил математику. Умные люди, объясните на пальцах или кодом, буду признателен.

Update: Обычно говорят, – и года не прошло. А вот у меня как раз прошел. Снова понадобилось, в этот раз подошел обстоятельно – вот код на PHP:

2 ответа 2

Предисловие

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

Алгоритм

Если учитывать и одиночные комбинации (A, B, C, D), то таких комбинаций всего 2 n – 1, где n – количество символов в исходной строке.

Допустим, что у нас строка из n символов. То есть, у нас n позиций в строке.

Рассмотрим каждую позицию нулём (0) либо единицей (1). Договоримся ставить 1 на той позиции, на которой мы хотим видеть символ, а 0 на той, на которой не хотим.

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

Эта строка кодирует комбинацию

А теперь выпишем двоичный набор длиной в n элементов

Этот набор выписывается достаточно просто. Если просто, то на каждой новой строке к последнему элементу прибавляется единица. И если в результате получается число больше единицы, то позиция обнуляется и единица добавляется на соседнюю слева позицию и т.д.

Этот набор (без первого) будет описывать всевозможные комбинации исходной строки.

Пример

Возьмём строку ABCD. В ней 4 символа, а значит, у нас будет 2 4 – 1 = 15 комбинаций.

Выпишем двоичный набор из 4 элементов

И получаем следующие варианты

Если вам не нужны одиночные комбинации, то можете их выбросить 🙂

Для начала – о терминах.
Возьмём для примера новогодние подарки. которых N штук в мешке.
Перестановки – когда эти подарки раскладывают на N полок (порядок важен).
Вариантов: N! .
Размещения – когда их пытаются разложить на M полок (попадают не все, порядок важен).
Вариантов: N! / M! .
Сочетания – когда их пытаются переложить в другой мешок (порядок неважен), в который входит только M штук.
Вариантов: N! / (M!(N-m)!) = C_N M .

Судя по постановке задачи (порядок неважен), речь идёт о сочетаниях, причём могут потребоваться либо они все (M = 1. N) либо диапазон в 2-3 элемента.

Программно реализована функция, которая может вызываться с разным числом параметров. Если на входе только массив символов, на выходе – все возможные сочетания. Но можно указать также M (один дополнительный параметр) или диапазон M (параметры from, to ).

Программа на PHP:

Заметим, что в соответствии с формулой бинома Ньютона суммарное число всех перестановок символизирует число (1+1) N . При N=4 это 16, но программа в первом варианте выдаёт 15. Чтобы баланс сходился, надо добавить к перестановкам пустую строку.