m个1,n个0的排列(高效率版).txt.txt

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

排列数为:c(m+n,n)
对n个0,m个1,我的想法是这样的:
每个排列可以分三段:
全0列,全1列, 子问题列
设各段长:r,s,t .子问题列就是 (n,m) = (n-r,m-s),其中0<=r<=n,s=1

0 0 0 0 0 1 1 1         1  

0 0 0 0 1 0 1 1         2
0 0 0 0 1 1 0 1         3
0 0 0 0 1 1 1 0         4

0 0 0 1 0 0 1 1         5
0 0 0 1 0 1 0 1         6
0 0 0 1 0 1 1 0         7
0 0 0 1 1 0 0 1         8
0 0 0 1 1 0 1 0         9
0 0 0 1 1 1 0 0         10

0 0 1 0 0 0 1 1         11
0 0 1 0 0 1 0 1         12
0 0 1 0 0 1 1 0         13
0 0 1 0 1 0 0 1         14
0 0 1 0 1 0 1 0         15
0 0 1 0 1 1 0 0         16
0 0 1 1 0 0 0 1         17
0 0 1 1 0 0 1 0         18
0 0 1 1 0 1 0 0         19
0 0 1 1 1 0 0 0         20

0 1 0 0 0 0 1 1         21
0 1 0 0 0 1 0 1         22
0 1 0 0 0 1 1 0         23
0 1 0 0 1 0 0 1         24
0 1 0 0 1 0 1 0         25
0 1 0 0 1 1 0 0         26
0 1 0 1 0 0 0 1         27
0 1 0 1 0 0 1 0         28
0 1 0 1 0 1 0 0         29
0 1 0 1 1 0 0 0         30
0 1 1 0 0 0 0 1         31
0 1 1 0 0 0 1 0         32
0 1 1 0 0 1 0 0         33
0 1 1 0 1 0 0 0         34
0 1 1 1 0 0 0 0         35

1 0 0 0 0 0 1 1         36
1 0 0 0 0 1 0 1         37
1 0 0 0 0 1 1 0         38
1 0 0 0 1 0 0 1         39
1 0 0 0 1 0 1 0         40
1 0 0 0 1 1 0 0         41
1 0 0 1 0 0 0 1         42
1 0 0 1 0 0 1 0         43
1 0 0 1 0 1 0 0         44
1 0 0 1 1 0 0 0         45
1 0 1 0 0 0 0 1         46
1 0 1 0 0 0 1 0         47
1 0 1 0 0 1 0 0         48
1 0 1 0 1 0 0 0         49
1 0 1 1 0 0 0 0         50
1 1 0 0 0 0 0 1         51
1 1 0 0 0 0 1 0         52
1 1 0 0 0 1 0 0         53
1 1 0 0 1 0 0 0         54
1 1 0 1 0 0 0 0         55
1 1 1 0 0 0 0 0         56


// ***************************************************************
//                       01排列
// ***************************************************************
//        version:  1.0    date: 06/12/2007
//  -------------------------------------------------------------
//         产生m个0,n个1的所有排列,并升序输出
//  -------------------------------------------------------------
//  algorithm :"全0列,全1列,子问题列"版
//  -------------------------------------------------------------
//  Language : c++    author : happynp   
// ***************************************************************
//  Copyright (C) 2007 - All Rights Reserved
// ***************************************************************
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
const int S = 100;
int   n1,n0,kCount,ans[S];
void Dfs(int m,int n,int offset) //m 0,n 1
{
   int  i;
   if(m==0)
   {
	    for(i=n0+n1;i>n0+n1-n;i--)
			ans[i] = 1;
		for(i=1;i<=n1+n0;i++)
		    printf("%d ",ans[i]);
		printf("\n");
   }
   else if(n==0)
   {	 
	    for(i=n0+n1;i>n0+n1-m;i--)
			ans[i] = 0;
		for(i=1;i<=n1+n0;i++)
		    printf("%d ",ans[i]);
		printf("\n");
   }
   else 
   { 
	 for(i=m;i>=0;i--)
	 {
		 for(int j=i;j>0;j--)
			ans[offset+j] = 0;
		 ans[offset+i+1] = 1;
		 Dfs(m-i,n-1,offset+i+1);
	 }
   }
}
int main() 
{ 
  while(scanf("%d%d",&n1,&n0))
  {
	 memset(ans,0,sizeof(ans));	 	 
	 Dfs(n1,n0,0);	 
  }
  return 0; 
}