Первая страница / Теория / Комбинаторика /

Комбинаторика (часть 1)

Голосование: 26, 7

Введение

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

При изучении различных комбинаторных объектов, мы, в первую очередь, будем отвечать на ряд классических вопросов:

  1. Сколько элементов содержит изучаемое множество?
  2. Каким образом можно перебрать элементы данного множества?
  3. Как можно перенумеровать эти элементы? Т. е. как, зная количество элементов n, сформировать взаимнооднозначное соответствие между элементами и числами 1:n?

Перебор 0-1 векторов

Для удобства, рассмотрим в качестве исследуемого комбинаторного объекта множество Bm наборов из m нулей и единиц. Для этого множества дадим ответы на поставленные вопросы.

Понятно, что множестве наборов из m нулей и единиц содержит ровно 2m элементов.

Для того, чтобы создать вычислительный процесс, при котором на каждом шаге будет формироваться новый, не встречавшийся ранее, элемент рассматриваемого множества, достаточно заметить, что существует взаимнооднозначное соответствие между числами из 0…2m−1 и наборами 0-1 векторов. Т. е. достаточно первым взять число 0 и его двоичное представление 0, …, 0, а затем просто добавлять по единице, имитируя это на текущем наборе, пока мы не дойдем до набора из одних единиц.

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

  1. Фиксируем нулевое значение m-й компоненты и перебираем все наборы длины m−1 для оставшихся компонент.
  2. Меняем значение m-й компоненты с 0 на 1. Перебираем наборы длины m−1 в обратном порядке.

Приведем таблицу, показывающую процесс перебора наборов длины 4. Столбец it показывает номер текущей итерации, а столбец kit — номер компоненты, которая подлежит обновлению.

Таблица

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

Коды Грея

Ранее мы рассматривали рекурсивный алгоритм перебора 0-1 наборов. Этот алгоритм позволяет перебирать все наборы Bm так, чтобы каждый следующий набор отличался от предыдущего только в одном разряде. Построенная с помощью этого алгоритма последовательность наборов (приводится в таблице) называется кодом Грея. Вообще, n-разрядный код Грея — это упорядоченная (возможно, циклическая) последовательность, состоящая из 2n n-разрядных кодовых слов, каждое из которых отличается от соседнего в одном разряде.

Приведем еще один (на этот раз нерекуррентный) алгоритм генерации кодов Грея. Будем рассматривать бинарные коды Грея порядка n. Итак, на вход алгоритма подается единственное число n, которое указывает порядок кода Грея. По ходу выполнения алгоритма мы получим последовательность всех подмножеств n-элементного множества, в которой каждое последующее подмножество получается из предыдущего добавлением или удалением единственного элемента (наименьшим возможным изменением) — код Грея. При этом каждое подмножество будет представляться бинарной последовательностью B[1], …, B[n].


Gray-Generation(n)
 1  for i := 1 to n do B[i] := 0;
 2  i := 0;
 3  repeat
 4      write (B[i], …, B[n]);
 5      i := i + 1; p := 1; j := i;
 6      while j mod 2 = 0 do
 7          begin
 8              j := j/2; p := p + 1;
 9          end;
10      if pn then B[p] := 1 − B[p];
11  until p > n   

Доказательство корректности работы алгоритма можно найти в [1].

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

Гамильтоновы пути

Перебор элементов прямого произведения множеств

Если мы рассматриваем два каких-либо множества A и B, то будем называть их прямым (декартовым) произведением (A×B) множеств A и B, множество всевозможных упорядоченных пар (ij), где i ∈ A, j ∈ B. Мощность же множества, получившегося при декартовом произведении множеств, будет равна произведению мощностей этих множеств.

Более того, мы можем определить прямое произведение любого конечного числа множеств. Например, если рассматривать экземпляры только одного множества, состоящего из двух элементов 0 и 1, то прямое произведение m таких экземпляров будет представлять собой ранее расcмотренное множество Bm.

Итак, рассмотрим прямое произведение k множеств: M1×M2×…×Mk. Очевидно, что

|M1×M2×…×Mk| = ∏i∈1:k mi,

где mi = |Mi| — количество элементов множества Mi.

Пусть множество Mi состоит из целых чисел от 0 до mi−1, i ∈ 1:k. Тогда каждый элемент прямого произведения M1×M2×…×Mk можно представить как последовательность неотрицательных чисел r1r2, …, rk, где 0 ≤ ri < mi.

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

num(r1r2, …, rk) = ∑i=1:k ri × ∏j=1:i−1 mj.

Перестановки

Перестановка n-элементного множества X — это взаимно однозначная функция fXX. Если для простоты принять X = {1, …, n}, то перестановкой можно назвать упорядоченный набор из n различных чисел, лежащих в промежутке от 1 до n (далее будет рассматриваться именно этот случай).

Обозначим множество всех перестановок множества X через Sn. Понятно, что |Sn| = n!, т. к. на первое место набора можно поставить любое число из n возможных, на второе — любое из n−1 оставшихся и т. д. до последней позиции, в которую мы помещаем последний оставшийся элемент: в результате, мы получим произведение, которое и будет являться факториалом n.

Рассмотрим множество Mi из предыдущей части. Пусть каждое Mi будет представлять собой множество чисел от 0 до i−1. Обозначим через Tn произведение n таких множеств. Тогда если будет существовать взаимнооднозначное соответствие между Sn и Tn, то мы сможем, в частности, перенумеровать все перестановки Sn. Предъявим механизм перехода от перестановки r1, …, rn ∈ Sn к элементу t1, …, tn ∈ Tn. Для этого для любого i ∈ 1:n найдем номер позиции s значения i в перестановке (rs = i) и примем в качестве ti количество элементов меньших i среди r1, …, rs−1. А при обратном переходе от элемента к перестановке, можно использовать то, что место любого элемента i (начиная с самого большого) на единицу больше, чем число элементов, предшествующих i, а само это число равно сумме ti и числа элементов, бОльших i.

Кроме того, каждую перестановку f ∈ Sn можно представить с помощью ориентированного графа с множеством вершин X = {1, …, n}, в котором ребро идет от x к у, когда f(x) = y. Легко можно показать, что такой граф состоит из некоторого числа элементарных циклов с различными множествами вершин, которые в сумме дают множество X. Т. е. каждую перестановку мы можем разложить на циклы. Например, рассмотрим перестановку f(1234567) = 7514236 и разобьем ее на циклы:

Циклы

Генерирование перестановок

Введем некоторые обозначения для записи алгоритмов. Элементы перестановки будем запоминать в виде элементов массива P[1], …, P[n]. Обмен значениями переменных будем обозначать через P[i] :=: P[j]. Напомним, что мы рассматриваем только перестановки, заданные на множестве X = {1, …, n}.

На множестве Sn зададим лексикографический порядок:

(x1, …, xn) < (y1, …, yn) ⇔ существует k ≥ 1, такое что xk ≤ yk и xl = yl для каждого l < k.

Аналогично задается антилексикографический порядок:

(x1, …, xn) < (y1, …, yn) ⇔ существует k ≤ n, такое что xk > yk и xl = yl для каждого l > k.

Теперь представим алгоритм генерации всех перестановок в антилексикографическом порядке. Заметим, что этот алгоритм является рекурсивным.


 1  procedure REVERSE(m); 
 2  begin i := 1; j := m;
 3      while i < j do
 4          begin P[i] :=: P[j]; i := i + 1; j := j - 1;
 5          end
 6  end

 7  procedure ANTYLEX(m);
 8  begin
 9      if  m = 1 then
10          write(P[1], …, P[n])
11      else 
12          for i := 1 to m do
13              begin ANTYLEX(m − 1);
14                  if i < m m then
15                      begin P[i] :=: P[m]; REVERSE(m − 1)
16                      end
17              end
18  end;

19  begin
20      for i := 1 to n do P[i] :=: i;
21      ANTYLEX(n)
22  end

Среднее число транспозиций, приходящихся на каждую перестановку, приблизительно равно 1.543, т. е. для порождения n! перестановок используется приблизительно 3.077n! сравнений.

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


 1  procedure B(m, i);
 2  begin
 3      if (m mod 2 = 0) and (m > 2) then
 4          if i < m − 1 then B := i
 5          else B := m − 2
 6      else B := m − 1
 7  end;

 8  procedure PERM(m);
 9  begin
10      if m = 1 then
11          write(P[1], …, P[n])
12      else
13          for i := 1 to m do
14              begin PERM(m − 1);
15                  if i < m then P[B(m, i)] :=: P[m]
16              end
17  end;

18  begin
19      for i := 1 to n do P[i] :=: i;
20      PERM(n)
21  end

Доказательство корректности алгоритма можно найти в [1].

Однако, существует еще более быстрый алгоритм генерирования перестановок, он строит последовательность перестановок, в которой каждая следующая образуется из предыдущей с помощью однократной транспозиции соседних элементов. Обозначим через PR[i] булеву переменную, содержащую информацию о том, переносится ли элемент i вперед (PR[i] = true) или назад. Переменнная C[i] будет показывать, какую из возможных ni+1 позиций элемент i занимает относительно элементов i+1, …, n на своем пути вперед и назад. Вот его код:


 1  begin
 2    for i := 1 to n do
 3        begin P[i] := i; C[i] := 1; PR[i] := true; 
 4        end;
 5    C[n] := 0;
 6    write(P[1], …, P[n]);
 7    i := 1;
 8    while i < n do
 9        begin i := 1; x := 0;
10            while C[i] = ni + 1 do
11                begin PR[i] := not PR[i]; C[i] := 1;
12                    if PR[i] then x := x + 1;
13                    i := i + 1;
14                end;
15            if i < n then
16                begin
17                    if PR[i] then k := C[i] + x;
18                    else k := ni + 1 − C[i] + x;
19                    P[k] :=: P[k + 1];
20                    write(P[1], …, P[n]);
21                    C[i] := C[i] + 1
22                end
23      end
24  end

На эту тему можно посмотреть визуализаторы [3] и [4].

Последовательность перестановок, полученная с помощью данного алгоритма имеет интересную интерпретацию. Так, если рассмотреть граф, вершины которого соответствуют всем перестановкам и в котором две вершины, соответствующие перестановкам f и g, соединены ребром, если g образуется из f однократной транспозицией соседних элементов, то полученная последовательность является гамильтоновым путем в этом графе. На рисунке изображен граф последовательности для n = 3, 4.

Циклы

Задача о минимуме скалярного произведения

Перестановки часто встречаются в самых различных областях математики и используются в разных задачах. Например, можно рассмотреть неалгебраическое использование перестановки в следующей экстремальной задаче: даны 2m чисел x1, …, xm и y1, …, ym, нужно найти такое разбиение чисел на пары (xiyj), при котором значение суммы, составленной из произведений чисел каждой пары, будет наименьшим.

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

Размещения и сочетания

Размещение из n элементов по m — это упорядоченный (здесь нам важен порядок) набор из m различных чисел, лежащих в промежутке от 1 до n (т. е. ∈ X). Другими словами размещение — это множество с повторениями. Обозначим число его элементов через An,m.

Для того, чтобы вычислить значение An,m, нужно следовать тем же рассуждениям, что и в случае с перестановками. Тогда получим следующий результат:

An,m = n! ⁄ (nm)!

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

Сочетание из n элементов по m — это неупорядоченный набор (множество) из m различных чисел, принадлежащих множеству X. Обозначим число элементов множества сочетаний через Cn,m.

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

Cn,m = n! ⁄ m!(nm)!

Можно привести некоторые свойства сочетаний:

  1. Cn,m = Cn,nm
  2. Cn,m + Cn,m+1 = Cn+1,m+1
  3. Cn,m * Cm,k = Cn,k * Cnk,mk

Эти свойства следуют из самих определений и проверяются непосредственно.

Теперь приведем алгоритм генерации сочетаний в лексикографическом порядке:


 1  begin
 2      for i := 1 to k do A[i] := i;
 3      p := k;
 4      while p ≥ 1 do
 5          begin write(A[1], …, A[k]);
 6              if A[k] = n then p := p − 1 else p := k;
 7              if p ≥ 1 then
 8                  for i := k downto p do A[i] := A[p] + ip + 1
 9          end
10  end

Доступен визуализатор [5] данного алгоритма.

Нумерацию сочетаний можно организовать, используя свойство 2) сочетаний, приведенное выше. Для этого с каждым сочетанием из n по m свяжем вектор из n нулей и единиц. В этом векторе будет m единиц, а числа сочетания будут задавать номера этих единиц. Тогда такому вектору можно, в свою очередь, сопоставить траекторию, в которой единицам соответствуют горизонтальный шаги, а нулям — вертикальные. Тогда формула для номера будет выгляеть, как

num(b[1:n], m) = { если b[n] = 0, то num(b[1:n−1], m); если b[n] = 1, то Cn−1,m + num(b[1:n−1], m−1)},

где b[1:n] — 0-1 вектор из n элементов.

Бином Ньютона

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

Треугольник Паскаля

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

(a + b)n = ∑k=0:n Cn,kakbnk

В этой формуле при раскрытии степени алгебраического двучлена коэффициенты при степенях совпадают с числом сочетаний. Исходя из формулы Ньютона значения Cn,m также еще называют биномиальными коэффициентами. Некоторые интересные свойства бинома Ньютона рассмотрены в [2].

Литература

  1. Липский В. Комбинаторика для программистов. — М.: Мир, 1988.
  2. Романовский И.В. Дискретный анализ. — 3-е изд. — СПб: Невский Диалект; БХВ Петербург, 2003.

Визуализаторы

  1. Михалев Е. Перебор перестановок (2000)
  2. Демин С. Перебор перестановок (2003)
  3. Белешко Д. Перебор сочетаний (2003)

Белешко Дмитрий


Михаил / 2004-12-06 13:29:08

Здравствуйте! Необходим алгоритм нумерации сочетаний. В частности не понятно как реализовывать фунцию num(b[1:n], m): <…>

В данном фрагменте статьи автор следует изложению материала в книге И.В.Романовского Дискретный анализ.

Собственно алгоритм можно реализовать, например, через рекурсивную процедуру с параметрами n и m, подставив в ее тело правую часть приведенного рекуррентного уравнения; значения вычленяемых слагаемых C[n,m] можно брать из треугольника Паскаля, заготовив предварительно соответствующую таблицу.

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

anonymous / 2008-10-18 02:47:25

Можно пояснить, что означает следующая строчка:

while C[i] = n − i + 1 do

Строчка означает: пока выполняется равенство "C[i] = n − i + 1", выполнять следующие инструкции.

Tou / 2010-02-01 15:40:31

взял алгоритм генерации сочетаний с этой страницы.

как я понял [...] есть соображения?

P.S. визуализации по ссылке [5] похоже визаулизирует ДРУГОЙ алгоритм. в ней мне непонятна терминология (напр., что значит слово "получаем" в "получаем первое сочетание" и др.), но так или иначе визуализация выдает другой результат.

Tou / 2010-02-01 15:46:04

прошу прощения за предыдущий пост.

[...] ошибся в реализации:)

Tou / 2010-02-07 20:36:56

Является ли этот алгоритм генерирования сочетаний самым быстрым из известных?

Формулировать так вряд ли можно. В отношении алгоритмов перебора комбинаторных объектов принято говорить об асимптотической трудоемкости, что, как правило, актуально лишь для наборов "большой" мощности.

николай / 2013-01-16 22:38:19

Нужен ( не даром ) быстрый алгоритм, написанный на Турбо Паскале для решения комбинаторной задачи.

Дан генератор действительных чисел a_1,...,a_k и целые n,k. Нужен алгоритм последовательного построения ВСЕХ ВОЗМОЖНЫХ чисел

вида a_1^{c_1}a_2^{c_2}...a_k^{c_k} где

c_1, c_2,,,c_k - целые, не отрицательные и c_1+c_2+...+c_к <=n.

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

я / 2013-03-08 21:42:45

Люди сходите к доктору. Он пропишет вам калькулятор!

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий