m个1,n个0的排列(dfs版).txt

排列问题 M个1,N个0的排列(高效率版) 排列数为:c(m+n,n) 对n个0,m个1,我的想法是这样的: 每个排列可以分三段: 全0列,全1列, 子问题列 设各段长:r,s,t .子问

#include <stdio.h>
#include <math.h>
#include <memory.h>
const int S = 52;
int   k,e[S],ans[S]; int nCount = 0;
__int64  v[S]={0};
bool  used[S];
void transform(int i)
{
   for(int j=1;j<=k;j++)
	  v[i] += ans[j]*pow(2,k-j);
}
void Dfs(int depth)
{
   int i;
   __int64 sum = 0;
   if(depth==k+1)
   { 
       for(i=1;i<=k;i++)
	     sum += ans[i]*pow(2,k-i);
	   for(i=0;i<nCount;i++)
	      if(sum == v[i])
			return;  
	   for(i=1;i<=k;i++)
		  printf("%d ",ans[i]);
       transform(nCount); 
	   printf("\t%d\n",++nCount);
   }
   else 
   { 
	 for(i=1;i<=k;i++)
	 {
		 if(used[i]==0 ) 
		 {	// && e[i]>ans[depth-1]
			//关键的剪枝 e[i] > ans[depth-1]使得每个排列内部是升序的,
			//这保证了以后出现的排列不会与先前产生的排列各元素都相同. 
			ans[depth] = e[i];
		    used[i] = 1;
            Dfs(depth+1);
		    used[i] = 0;
		 }
	 }
   }
}
int main () 
{ 
  int i,m,n;
  bool IsFirst = true;
  while(EOF!=scanf("%d%d",&m,&n)) //m个1,n个0
  {
	 k = m + n;   
	 if(k==0)
		break;
     for(i = 1;i<=k;i++)
		if(i<=m)
          e[i] = 0;
		else
		  e[i] = 1;	
     nCount = 0;
	 memset(ans,0,sizeof(ans));
	 memset(used,0,sizeof(used));
	 memset(v,0,sizeof(v));
	 if(IsFirst)
        IsFirst = false;
	 else
        printf("\n");	 	 
	 Dfs(1);	 
  }
  return 0; 
}