Основные элементы комбинаторики Комбинаторика

Основные элементы комбинаторики
Комбинаторика
Комбинаторика, как можно судить по названию, - раздел математики, изучающий различные комбинации объектов и множеств. Комбинаторика очень тесно связана с информатикой, и часто встречается в олимпиадных задачах. Она включает в себя множество понятий, но в программировании чаще всего используются две из них:
Перестановки
Когда две последовательности состоят из одинаковых объектов, расположенных в разном порядке, они называются перестановками одной и той же последовательности. Например, для последовательности 1,2,31,2,3 существует 6 перестановок:

• 
  1,2,31,2,3.
  
• 
  1,3,21,3,2.
  
• 
  2,1,32,1,3.
  
• 
  2,3,12,3,1.
  
• 
  3,1,23,1,2.
  
• 
  3,2,13,2,1.
  

Рассчитать число существующих перестановок достаточно просто. На первое место может стать один из NN элементов. На второе место - один из N−1N−1 оставшихся. На третье N−2N−2, и так далее. На последнее место может стать только один элемент, нигде до этого не использовавшийся. Значит, количество перестановок последовательности длиной NN равно
PN=1∗2∗…∗N=∏i=1Ni=N!PN=1∗2∗…∗N=∏i=1Ni=N!
Факториал, по определению, и является количеством перестановок последовательности длиной NN.
Более интересная алгоритмически задача: вывести все перестановки заданной последовательности. Наивный алгоритм её решения является достаточно эффективным, и является отличным примером распространённого подхода рекурсивного перебора.
Суть алгоритма проста. Обозначим изначальную последовательность aa. Определим рекурсивную функцию f(i1,i2,…,ik)f(i1,i2,…,ik). Вызов этой функции должен вывести все перестановки последовательности aa, начинающиеся с чисел a[i1],a[i2],…,a[ik]a[i1],a[i2],…,a[ik].
Крайний случай рекурсии очевиден: если k=Nk=N, то a[i1],a[i2],…,a[ik]a[i1],a[i2],…,a[ik] и есть одна из перестановок. Просто выведем её. Во всех других случаях поступаем следующим образом: пусть j1,j2,…,jN−kj1,j2,…,jN−k - ещё не использованные индексы. По очереди рекурсивно вызовем f(i1,i2,…,ik,j1)f(i1,i2,…,ik,j1), f(i1,i2,…,ik,j2)f(i1,i2,…,ik,j2), ……, f(i1,i2,…,ik,jN−k)f(i1,i2,…,ik,jN−k). Таким образом мы гарантированно переберём все возможные перестановки.
На практике передача в функцию такого большого числа аргументов - плохая идея, поэтому функция реализуется по-другому. Просто будем поддерживать глобальный вектор vv, в который по мере углубления рекурсии будем добавлять элементы текущей перестановки. Кроме него также будем поддерживать глобальный массив usedused: если при вызове функции f для какого-либо ii выполняется условие used[i]used[i], это значит, что индекс ii уже был использован.
Реализация на C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41