9.4 Генерация сочетаний

Сочетанием элементов из E = {a1, . . . , an} по k называется упорядоченное подмножество из k элементов, принадлежащих E и отличающихся друг то друга составом, но не порядком элементов.

Число сочетаний вычисляется по формуле

(9.3)

Существует множество различных алгоритмов генерации сочетаний, ниже будет описан алгоритм генерации, основанный на нумерации сочетаний. Для этого запишем следующие тождества:

(9.4)

(9.5)

Применяя тождество (9.5) для заданного сочетания , можно построить двоичное дерево(рис. 9.2).

Дерево строится до тех пор, пока каждый лист этого дерева не станет элементом тождества (9.4). Очевидно, что число листьев такого дерева равно .

Пример такого дерева записан для представления сочетания на рис. 9.3.

Рис. 9.3. Пример двоичного дерева декомпозиции для сочетания

Количество листьев равно 6, что соответствует числу сочетаний. Заметим, что количество путей из корня этого дерева до листьев равно числу сочетаний. Можно попытаться связать конкретный путь в дереве с некоторым элементом сочетания. Для этого пронумеруем выходные дуги: для левой дуги поставим «0», для правой дуги - «1». Тогда, производя левосторонний обход дерева (см. рис. 9.3) и записывая соответствующие цифры для каждого пути, получим

Для первой строчки не хватает двух единиц, для второй - одной единицы, для третьей - нуля, для четвертой - единицы, для пятой - нуля, для шестой - двух нулей.Можно предложить следующее правило дописывания единиц или нулей. Eсли лист содержит m, равное n, то справа дописывается m единиц. Eсли лист содержит m, равное нулю, то справа дописывается n нулей. Используя эти простые правила, можно перечислить все сочетания для заданных значений m и n. Теперь построим алгоритм генерации сочетания по трем параметрам , где m, n - параметры сочетания, а k - номер сочетания. Очевидно, что для k должно выполняться следующее соотношение:

Необходимо для заданного k найти k-й путь в двоичном дереве. Решающее правило будет следующее:
1) если то записываем ноль и переходим на рассмотрение узла
2) если , то записываем единицу, вычисляем и переходим на рассмотрение узла
3) повторяем эти действия, пока не достигнем листа.

Назовем этот алгоритм GCombination.

Реализация алгоритма

Функция вычисления количества сочетаний

int Comb (int n,int m)
{
      int k=(n-m<m)?m:n-m;
      int l=(n-m>=m)?m:n-m;
      int v=1;
      for (int j=1, i=k+1; i<=n; i++, j++){
            v*=i;
            v/=j;
      }
      return v;
}

Функция генерации сочетания по номеру. На входе v - вектор, элементы которого принимают значения 0 или 1. Параметр top – номер текущей позиции в векторе, k - номер сочетания, n и m – параметры сочетания.

void GenerateCombination (int v[ ],int top,int k,int n,int m)
{
      int b;
      if (m==0){
            for (int i=0; i<n; i++) v[top++]=0;
            return;
      }
      if (m==n){
            for (int i=0; i<n; i++) v[top++]=1;
            return;
      }
      b=Comb(n-1, m); //вычисление сочетания
      if (k <= b) { v[top++]=0 ; GenerateCombination(v,top,k,n-1,m);}
      else
      {
            v[top++]=1; GenerateCombination(v,top,k-b,n-1,m-1);
      }
      return;
}