Раздел «Алгоритмы».GenerateCPP:

Переборные алгоритмы n!, 2^n, C(n,m) на C

Содержание

Перебор 2^n — все подмножества

Дано n-элементное множество. Нужно перебрать все подмножества. Количество подмножеств n-элементного подмножества равно 2^n.

M = intpower(2,n);
for(i=0; i < M; i++ )
{
   int a = i;
   // a — зашифрованное подмножество
   // j-й бит числа a соответствует j-у элементу
   for(j=0; j < n ; j++)
   {
      if(a%2){
         // берем элемент с номером j
      }
      a /=2;
   }
}

В более обшем случае приходится исмользовать массив A, в котором ранить нули и единицы.

Удобнее всего для перебора использовать рекурсивные функции.

int A[M] = {0,..};
void gen_2n(int i)
{
    if(i==n) {
        // рассматриваем подмножество, задаваемое массивом A
    }
    A[i] = 1; gen_2n(i+1);
    A[i] = 0; gen_2n(i+1);
}

Перебор C^m_n — все k-элементные подмножества

Для решения данной задачи подмножества удобнее представлять в виде упорядоченного набора из k номеров элементов.

// Максимальное значение m
#define M 100   

int m,n;
int A[M+1] = {0,..};

void genCnm(int i)
{
   if(i > m) {
       // рассматриваем подмножество, задаваемое массивом A
   }
   for(j=A[i-1]; j < n ; j++)
      {
          A[i] = m; genCnm(i+1);
      }
}
main()
{
    scanf("%d%d", &k, &n);
    gen_Cnm(1);
}

Перебор n!

int A[M] = {0,..};
int n;
void gen_Fact_n(int i)
{
   if(i==n) {
       // рассматриваем подмножество, задаваемое массивом A
   }
   for(j=0; j < n ; j++)
      if(!was[j])
      {
         was[j] = 1; 
         A[i] = j; gen_Fact_n(i+1);
         was[j] = 0;
      }
}
main()
{
   scanf("%d", &n);
   gen_Fact_n(0);
}

AlgorithmClasifyForm
Type: Код
Scope:  
Strategy:  
Complexity: Low