Название: Алгоритмы - Учебное пособие ( Редактор )

Жанр: Экономика

Просмотров: 1730


3.1.  генерация k-элементных подмножеств

В комбинаторике такие подмножества называют сочетаниями из n элементов по k элементов и обозначают Cnk . Их количество выражается следующей формулой:

      .      (1)

Однако при программировании гораздо удобнее использовать следующие рекуррентные соотношения:

     

        (2)

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

При фиксированном значении n максимального значения число сочетаний достигает при k = n/2 (вернее, для четного n максимум один и он указан, а для нечетного — максимум достигается на двух соседних значениях k: [n/2] и [n/2]+1). Поэтому особенно полезной оказывается следующая оценка для четных n [4] (очевидно, что при нечетных n отличия будут минимальными), основанная на формуле Стирлинга:

      (3)

3.1.1.  Задача о числе сочетаний

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

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

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

Чемпионат по футболу. В чемпионате по футболу России принимают участие 17 команд, они разыгрывают  золотые, серебряные и бронзовые медали. Команды победительницы примут участие в Европейском чемпионате. Сколько различных способов представительства нашего государства на Европейском турнире?

3.1.2.  Вычисление 

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

Для вычисления числа сочетаний из N по K использование формулы (1) явно не продуктивно. Факториал представляет собой быстровозрастающую функцию, поэтому при вычислении числителя и знаменателя дроби может возникнуть переполнение, хотя результат – число сочетаний – не превышает значения  MaxInt. Поэтому для подсчета числа сочетаний используем формулу (2).

Получаем известный треугольник Паскаля (рис. 3.1)

К ®

0

1

2

3

4

5

6

7

8

9

0

1

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

0

0

0

0

0

2

1

2

1

0

0

0

0

0

0

0

3

1

3

3

1

0

0

0

0

0

0

4

1

4

6

4

1

0

0

0

0

0

5

1

5

10

10

5

1

0

0

0

0

6

1

6

15

20

15

6

1

0

0

0

7

1

7

21

35

35

21

7

1

0

0

8

1

8

28

56

70

56

28

8

1

0

9

1

9

36

84

126

126

84

36

9

1

 

Рис. 3.1

 

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

Алгоритм вычисления числа сочетаний из N  по  K

Longint A,B [MaxN] /* А – значения  предыдущей строки треугольника Пасаля. В – значения текущей строки треугольника Паскаля */

 Число_сочетаний  (K)

A¬ 0 /* присвоить всем элементам массива А нулевые 

значения */

B¬ 0 /* присвоить всем элементам массива B нулевые 

значения */

A[0] ¬ 1; A[1] ¬ 1;

For (i¬1; i £ N; i¬i+1) {

B[0] ¬ 1; B[1] ¬ 1;

For (j¬1; j £ K; j¬j+1)

B[j] ¬ A[j] + A[j-1]; /* Если число больше максимального значения типа LongInt, то необходимо работать с «длинной» арифметикой. */

A ¬ B /* текущее значение становится предыдущим */

}

Число сочетаний ¬ A[K]

Алгоритм полного вычисления треугольника Паскаля

Const MаxN = 100

LongInt T[MaxN+1][MaxN+1] /* добавляется нулевой столбец и нулевая строка. Это позволяет обойтись без анализа выхода за пределы массива*/

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

{

T¬ 0 /* присвоить всем элементам массива T нулевые 

значения */

For (i¬0; i £ N; i¬i+1) T[i,0]¬ 1;     /* В первый столбец

таблицы записываем значения 1*/

For (i¬1; i £ N; i¬i+1)

For (j¬1; j £ K; j¬j+1)

If (T[i–1,j]*1.0 + T[i–1, j–1] > MaxLongInt) Exit /* переполнение*/

Else T[i,j]¬T[i-1,j] +T[i-1,j-1] /*

}

3.1.3. Генерация всех сочетаний

в лексикографическом порядке

Если допустить, что за время, отведенное для решения задачи, мы можем перебрать около 106 вариантов, то из формулы (3) следует, что генерацию всех сочетаний из n элементов для любого фиксированного k  можно проводить для  n £ 24.

Обычно генерацию всех k-элементных подмножеств проводят в лексикографическом порядке. Напомним, что порядок подмножеств называется лексикографическим, если для любых двух подмножеств справедливо, что ранее должно быть сгенерировано то из них, из индексов элементов которого можно составить меньшее k-значное число в n-ричной системе счисления (или в десятичной, для n < 10). Так, для n = 6 и k = 3 сочетание из третьего, первого и пятого элементов должно быть сгенерировано раньше, чем из второго, третьего и четвертого, так как 135 < 234.

Задача. Построить К-элементные подмножества из множества мощности N (табл. 3.1).

Например, K = 5, N = {1,2,3,4,5,6,7}, число сочетаний равно 21.

 

Таблица 3.1

0

{1,2,3,4,5}

7

{1,2,4,5,7}

14

{1,4,5,6,7}

1

{1,2,3,4,6}

8

{1,2,4,6,7}

15

{2,3,4,5,6}

2

{1,2,3,4,7}

9

{1,2,5,6,7}

16

{2,3,4,5,7}

3

{1,2,3,5,6}

10

{1,3,4,5,6}

17

{2,3,4,6,7}

4

{1,2,3,5,7}

11

{1,3,4,5,7}

18

{2,3,5,6,7}

5

{1,2,3,6,7}

12

{1,3,4,6,7}

19

{2,4,5,6,7}

6

{1,2,4,5,6}

13

{1,3,5,6,7}

20

{3,4,5,6,7}

 

Рекурсивная процедура решения данной задачи.  Идея сведения данной задачи к задаче меньшей размерности следующая. Первым элементом подмножества может быть любой элемент, начиная с первого и заканчивая (n – k + 1)-м элементом. После того как индекс первого элемента подмножества зафиксирован, осталось выбрать k – 1 элемент из элементов с индексами большими, чем у первого. Далее поступаем аналогично. Выбрав последний элемент, мы достигли конечного уровня рекурсии и выбранное подмножество можно обработать (проанализировать или распечатать). В предлагаемой ниже программе массив a содержит значения элементов исходного множества и может быть заполнен произвольным образом. В массиве p будем формировать очередное сочетание из k элементов.

 

const nmax = 24;

int a,p[nmax];

int  k,i,j,n,q;

 Печать (k ,p)

{

  For (i¬1; i £ k; i¬i+1)

    печатать(p[i]);

}

 

Сnk(n,k );

 Gen(m,L );

 {

    1   if( m=0 ) Печать(k, р)

       else

    2   For (i¬L; i £ N –m+1; i¬i+1)

       {

    3     p[k-m+1] ¬a[i];

    4    Gen(m-1,i+1)

       }

 };/*gen*/

 

{ /*cnk*/

  1  gen(k,1)

};/*cnk*/

{ /*main*/

  1  читать (n,k);

  2  For (i¬1; i £ N; i¬i+1)

  3  a[i]¬i;/*заполнить массив можно и по-другому*/

  4  cnk(n,k)

}

 

Заметим, что собственно генерация сочетаний производится в рекурсивной подпрограмме Gen. Она имеет следующие параметры: m – сколько элементов из множества нам еще осталось выбрать и L – начиная с какого элемента исходного множества, следует выбирать эти m элементов.

 

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

 

Следующее_сочетание (P);

{ i¬ k;

while ( P[I]+k-I+1 > N) i¬i-1;/* находим элемент, который можно увеличить*/

P[i]¬ p[i] + 1;       /* увеличиваем найденный элемент

на единицу */

For (j ¬ i+1; j £ k;  j ¬ j+1) P[j] ¬ p[j-1] + 1; /*Изменение стоящих справа элементов */

}