组合算法之01转换法

import java.util.ArrayList;
import java.util.List;

/**
 * 组合算法: 01转换法
 * 求从数组a[1..n]中任选m个元素的所有组合(无重复)
 *
 * 所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。
 * 组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。
 * 解决组合问题的通用算法不外乎递归和回溯（就是穷举法）两种。
 *
 */
public class Combination {

 int arr[]=new int[]{1,3,5,7,4,};
 int n=3;
 int m=arr.length;
 
 int newArr[];
 List result=new ArrayList();
 /**
  * 从数组arr中取出n个数的组合（无重复）
  * 1代表取，0表示不取
  *
  */
 public static void main(String[] args) {
  Combination c=new Combination();
  
  c.combin();
 }
 
 void combin(){
  newArr=new int[m];
  for(int i=0;i<m;i++){
   if(i<n){
    newArr[i]=1;//从长度为的数组中取出n个数的组合：11100   前面n个1
   }
   else{
    newArr[i]=0;
   }
  }
  
  boolean isExit=true;
  do{
   prt();
   for(int k=m-n;k<m;k++){//最后一个组合，1全在右边
    isExit=false;
    if(newArr[k]!=1){
     isExit=true;
     break;
    }
    
   }
   //10转换01，通过11100 把10循环转换01，直到变为00111结束
   for(int j=0;j<m-1;j++){
    if((newArr[j]==1&&newArr[j+1]==0)){
     newArr[j]=0;
     newArr[j+1]=1;
     break;
    }
   }
  }while(isExit);
  
 }
 //根据newArr数组取出1对应的arr数组的值
 void prt(){
  int ac[]=new int[n];

  int num=0;
  for(int i=0;i<m;i++){
   if(newArr[i]==1){
    System.out.print(arr[i]);
    ac[num++]=arr[i];
   }
  }
  result.add(ac);//取n位的所有组合（无重复：135表示了315，153，351，513，531）
  System.out.println();
 }

}