排列组合Java版

package net.highersoft.service;

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

public class PaiLie {

    /**
    * @param args
    */
   public static void main(String[] args) {
      
       printCount(3,2);
       
       List<Integer> src=new ArrayList();
       src.add(3);
       src.add(4);
       src.add(6);
       
      
       System.out.println("原数:"+src);
       List<List<Integer>> s=getTheNumAll(src,2);
       System.out.println("-------A(3,2) start----------");
       for(int i=0;i<s.size();i++){
           List<Integer> t=s.get(i);
           for(Integer c:t){
               System.out.print(c+"\t");
           }
           System.out.println();
       }        
       System.out.println("-------A(3,2) end----------");
       
       
       
       
       Integer srcs[]=new Integer[] {3,4,5,6,7};
       int selectNum=3;
       List<Object[]> result=combinationSelect(srcs, 0, new Object[selectNum], 0);
       
       System.out.println("-------C("+srcs.length+","+selectNum+") start----------");
       for(Object[] tmp:result){            
           System.out.println(Arrays.asList(tmp));
       }
       System.out.println("-------C("+srcs.length+","+selectNum+") end----------");
       
       
   }
   public static void printCount(int total,int sel) {       
       long sum=1;
       for(int i=total;i>=total-sel+1;i--){
           sum*=i;
       }
       System.out.println("A ("+total+","+sel+")="+sum);
      
       long div=1;
       for(int i=1;i<=sel;i++){
           div*=i;
       }
      
       System.out.println("C ("+total+","+sel+")="+sum/div);
   }
  
   private static List<List<Integer>> getTheNumAll(List<Integer> src,int n){
       if(n<1){
           List l=new ArrayList();
           //l.add(src);
           return l;
       }
       List<List<Integer>> ret=new ArrayList();
       for(int i=0;i<src.size();i++){
           int cur=src.get(i);
           List tmp=new ArrayList();
           tmp.addAll(src);
           tmp.remove(i);   
          
           List<List<Integer>> lastRet=getTheNumAll(tmp,n-1);
          if(lastRet.size()>0){
               for(int j=0;j<lastRet.size();j++){
                   lastRet.get(j).add(0, cur);
               }
           }else{
               List l=new ArrayList();
               l.add(cur);
               lastRet.add(l);
           }
           ret.addAll(lastRet);
          
       }
       return ret;
   }
   
   
   
   /**
    * 生成所有组合
    * @param source 原始数据，从这些数据中选
    * @param waitSelectIndex 待选开始索引
    * @param selectedResult 前面（waitSelectIndex-1）个的组合结果
    * @param currentSelectIndex 选择索引，从0开始
    * @return
    */
   private static List<Object[]>  combinationSelect(Object[] source, int waitSelectIndex, Object[] selectedResult, int currentSelectIndex) {
	  
       int selectIndex = currentSelectIndex + 1;
       if (selectIndex > selectedResult.length) { // 全部选择完时，输出组合结果
    	   List<Object[]> result=new ArrayList<Object[]>();
    	   Object tmp[]=new Object[selectedResult.length];
           System.arraycopy(selectedResult, 0, tmp, 0, tmp.length);            
           result.add(tmp);
           return result;
       }

       List<Object[]> rstList=new ArrayList<Object[]>();
       /**
        *  递归选择下一个
        *  selectedResult已选数组长度始终一样
        *  这样第1位最大值是n-r+1、第2位最大值为n-r+2 ... 第r位最大值为n-r+r(即n)
        */
       for (int i = waitSelectIndex; i < source.length - selectedResult.length + selectIndex; i++) {
    	   selectedResult[currentSelectIndex] = source[i];
           List<Object[]> rst=combinationSelect(source, i + 1, selectedResult, currentSelectIndex + 1);
           rstList.addAll(rst);
       }
       return rstList;
   }
}