9.5 Генерация размещений

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

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

или

(9.6)

Легко заметить, что

(9.7)

Таким образом, число размещений из n по k есть число сочетаний из n по k, умноженное на число перестановок размером k. Используя это свойство, можно предложить следующий алгоритм генерации размещений.

Дано: множество элементов, представленное вектором v[n] , k - количество элементов в размещении, i - номер размещения, для которого выполняется условие

Необходимо получить i-е размещение.

1. Вычисляем номер сочетания
2. Вычисляем номер перестановки
3. Генерируем сочетание z = GCombination(v, n, k) .
4. Генерируем перестановку s = GPermutation(z, k) .
5. Получаем s - i-е размещение из n элементов по k.

Реализация алгоритма генерации размещений по номеру.

Функция вычисления количества размещений из n по m

int Arran(int m, int n)
{
      int v=1;
      for(int i=n-m+1; i<=n; i++) v=v*i;
      return v;
}

Функция генерации размещения

void GenerateArrengment(int v[ ], int m, int n, int k)
{
      int c[100];
      int p[100];
      int num_comb=k/Factorial(m); //k%Comb(n,m);
      int num_perm=k%Factorial(m); //k/Comb(n,m);
      //printf("k %d %d %d \n",k,num_comb+1,num_perm);
      GenerateCombination(c,0,num_comb+1,n,m);
      //PrintPermut(c,n);
      GeneratePermutation(p,m,num_perm);
      //PrintPermut(p,m);
      int top=0;
      for(int i=0; i<n; i++)
            if(c[i]==1) c[top++]=i;
            //PrintPermut(c,top);
      for(int i=0; i<m; i++) v[i]=c[p[i]-1];
}