排列组合 递归和非递归算法实现

一、全排列的递归算法

       例如：一组数 A B C D

                 结果就是 A开头的全排列

                                ---B和C和D开头的全排列

                                ---------------C和D开头的全排列

                                ---------------------------- D开头的全排列

                                B开头的全排列

                                C开头的全排列

                                D开头的全排列

                 后面N-1个元素分别于第N元素交换，当数组只有一个的时候便是出口了。

	public static void full_array_test1(char[] a,int start,int end){
	  //首先当start=end的时候结束那个递归
		if(start==end){
			FULL_ARRAY_COUNT++;
			for(int i=0;i<=end;i++){
				System.out.print(a[i]+" ");
			}
			System.out.println();
		}else{
			//下一个元素交换
			for(int i=start;i<=end;i++){
				char temp=a[start];
				     a[start]=a[i];
				     a[i]=temp;
				//递归下一个
				     full_array_test1(a,start+1,end);
			    //还原数据
				     temp=a[start];
				     a[start]=a[i];
				     a[i]=temp;
			}
		}
	}

 二、非递归方法

 

 

1.前提是排过序的 从小到大   例如：12345

2.那么最大的值是                              54321

                                              那么：21345 的下一个数是：21354

                                                                        下一个数是：21435

3.那么位置在这两个中间的就是我们要求的

------------------------------------1.判断是否到终点了，就是一个最大的排列。

                                              判断方法从右边到左边如果不是递增的就ok  记录下位置index

 -----------------------------------2.根据上面提供的index然后确保找到比index-1《index2《index的一个最小值

 -----------------------------------3.交换1和2产生的位置的值

 -----------------------------------4.在交换位置的地方1的值后面 需要倒排

                                            （因为后面是递减的，转换后是递增，然后从新排列）

 -----------------------------------5.输出排列的组合

 //从最右边判断是否右边的数有比较左边的数大的有的话说明这个这个数有后继者
	public static int indexBig(char[] a){
		int index=-1;
		for(int j=a.length-1;j>=1;j--){
			if(a[j]>a[j-1]){
				index=j;
			break;
			}
		}
		return index;
	}
	//有后继者后得到了 右边比左边的数大的位置了 然后查找比一个最小的比他大的数
	public static int indexMinMax(char[] a,int indexMax){
		int index=indexMax;
		char temp=a[indexMax];
		for(int i=indexMax;i<a.length;i++){
			if(a[i]>a[indexMax-1]&&a[i]<temp){
				index=i;
				temp=a[i];
			}
		}
		return index;
	}
////交换
	public static void change(char[] a,int i ,int j){
		char temp=a[i];
		    a[i]=a[j];
		    a[j]=temp;
	}
	//对于交换的数位置之后的数进行倒叙排列 其实是一个排序
	//应该怎么进行的哪？
	public static void oppsiteDirectory(char[] a,int index){
		 
		for(int i=index;i<((a.length-index)/2+index);i++){
		 char temp=a[i];
		      a[i]=a[a.length-1-(i-index)];
		      a[a.length-1-(i-index)]=temp;
		}
	}
	//输出字符数组的
	public static void print(char[] a){
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+"　");
		}
		System.out.println();
	}

 

 

 

               String ss="123456";
		a=ss.toCharArray();
		print(a);

		int index1=-1;
	        int index2=-1;
	    int count=1;
		while(true){
			//首先检测
			
		    index1=indexBig(a);
			if(index1==-1)
				break;
			index2=indexMinMax(a, index1);
			change(a, index1-1, index2);
			oppsiteDirectory(a, index1);
			print(a);
			count++;
		}
		System.out.println(count);

 

 三、组合的算法

//递归算法
static void combine( int a[],int n,int m,int b[] )
	{ 
	 for(int i=n; i>=m; i--)  
	 {
	  b[m-1] = a[i-1];
	  if (m > 1)
	   combine(a,i-1,m-1,b);
	  else                    
	  {   
	   System.out.println(Arrays.toString(b));
	  }
	 }
	}

 

//按照网上的10转换
	//输出有10的位置第一次位置 
	//然后调整为01
	//10左边的移动到左边
	static void combine2(int[]a,int n,int m,int[] b){
	 for(int i=0;i<m;i++)
		 b[i]=1;
	 do{
		 printArray(b,a);
	 }while(getFirstFlage(b,n,m)!=-1);
	}
	
	static int getFirstFlage(int[]b,int n,int m){
		int count=0;
		for(int i=0;i<n-1;i++){
			
			if(b[i]==1&&b[i+1]==0){
			     	//交换位置
				    b[i]=0;
				    b[i+1]=1;
				    //移动
				    for(int j=0;j<count;j++){
				    	b[j]=1;
				    }
				    for(int k=count;k<i;k++)
				    	b[k]=0;
				   // System.out.println(count+"=="+Arrays.toString(b));
				 return i;
			}else if(b[i]==1){
				count++;
			}
		}
		return -1;
	}
	static void printArray(int[]b,int[]a){
		for(int i=0;i<b.length;i++){
			if(b[i]==1)
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
	 
	    int[] a=new int[]{1,2,3,4,5,6,7,8};
	    int[] b=new int[8];
	    combine2(a,a.length,3,b);
		//combine(a,a.length,2,b);
		//System.out.println("总的个数："+k);
	}