sort.txt

经典的剪枝

·排列组合算法     -|liuyukevin 发表于 2007-6-3 15:56:00  
 

1.n个数的全排列
＃i nclude <stdio.h>
const int N = 5;
int a[N] = {1,2,3,4,5};
void swap(int &a,int &b)
{
  int t ;
  t = a;
  a = b;
  b = t;
}
void permutation(int m,int n)
{
  int i;
  if(m==n)
  {
     for(i = 0;i<=n;i++)
     {
       printf("%d ",a[i]);
     }
     printf("\n");
  }
  for(i = m;i<=n;i++)
  {
    swap(a[i],a[m]);
    permutation(m+1,n);
    swap(a[i],a[m]);
  }
}
int main()
{
  permutation(0,4);
}


2.n取r的排列
＃i nclude <stdio.h>
const int N = 5;
int a[N] = {1,2,3,4,5};
int b[N];
int r = 3;
char used[N];
void perm(int pos)
{
  int i;
  if(pos==r)
  {
    for(i = 0;i<r;i++)
     {
       printf("%d ",b[i]);
     }
    printf("\n");
  }
  for(i = 0;i<N;i++)
  {
     if(!used[i])
     {
        b[pos] = a[i];
        used[i]++;
        perm(pos+1);
        used[i]--;
     }
     
  }       
}
int main()
{
  perm(0);
}
3.n取r的组合
＃i nclude <stdio.h>
const int N = 9;
int a[N] = {1,2,3,4,5,6,7,8,9};
int b[N];
int r = 4;
char used[N];
int count;
void combine(int pos)
{
  int i;
  if(pos==r)
  {
     for(i = 0;i<r;i++)
     {
       printf("%d ",a[b[i]]);
     }
    printf("\n");
    count++;
    return;
  }
  //这里是关键，第i个位置上的数，只能是从排在第i位的数开始的N-r个中的一个，后面的数一定要比前面的大 
  for(i = (pos>0?(b[pos-1]+1):pos);i<=pos+N-r;i++)   
  {
    if(!used[i])
    {
      b[pos] = i;
      used[i]++;
      combine(pos+1);
      used[i]--; 
    }
  }
}
int main()
{
combine(0);
}