排列组合算法一

package net.highersoft.service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * 排列组合
 * @author chengzhong
 *
 */
public class PermutationCombination {

	public static void main(String[] args) {
		List<Integer> items=Arrays.asList(new Integer[] {6,2,3,4,5});
		permutation(new ArrayList<Integer>(),items,3);
		System.out.println("总排列数:"+permutationNum);
		
		combination(new ArrayList<Integer>(),items,3,0);
		System.out.println("总组合数:"+combinationNum);
		List<List<Integer>> objs=combinationObj(items,2);
		System.out.println("C(5,2)=10:");
		for(List obj:objs) {
			System.out.println(obj);
		}
	}
	
	/**
	 * 字典序，即数字从1开始。第r位最大为n,第r-1位最大为n-1   ...    第1位最大为n-r+1
	 * @param head
	 * @param items
	 * @param chooseNum
	 */
	private static void combination(List<Integer> head, List<Integer> items, int chooseNum,int curIndex) {
		int maxIndex=items.size()-chooseNum+curIndex;
		for(int i=curIndex;i<=maxIndex&&i<items.size();i++) {
			Integer item=items.get(i);
			List<Integer> newHead=new ArrayList<Integer>();
			newHead.addAll(head);
			newHead.add(item);
			if(newHead.size()==chooseNum) {
				System.out.println(newHead);
				combinationNum++;
				continue;
			}
			combination(newHead,items,chooseNum,i+1);
		}
		
	}
	
	/**
	 * 能通用各种类型的方法
	 * @param <T>
	 * @param items 原始数据
	 * @param chooseNum 选择几个数
	 */
	public  static  <T> List<List<T>> combinationObj(List<T> items, int chooseNum) {
		List rst=new ArrayList();
		combinationObj(items, chooseNum,null,null,rst);
		return rst;
	}
	private static void combinationObj(List items, int chooseNum,List head,Integer curIndex,List rst) {
		if(rst==null) {
			rst=new ArrayList();
		}
		if(head==null) {
			head=new ArrayList();
		}
		if(curIndex==null) {
			curIndex=0;
		}
		int maxIndex=items.size()-chooseNum+curIndex;
		for(int i=curIndex;i<=maxIndex&&i<items.size();i++) {
			Object item=items.get(i);
			List<Object> newHead=new ArrayList<Object>();
			newHead.addAll(head);
			newHead.add(item);
			if(newHead.size()==chooseNum) {
				rst.add(newHead);
				continue;
			}
			combinationObj(items,chooseNum,newHead,i+1,rst);
		};
		
		
	}

	static int permutationNum=0;
	static int combinationNum=0;
	public static void permutation(List<Integer> head,List<Integer> items,int chooseNum){
		if(chooseNum==0) {
			System.out.println(head);
			permutationNum++;
			return;
		}
		
		for(Integer item:items) {
			//System.out.print(item+"->");
			List<Integer> newHead=new ArrayList<Integer>();
			newHead.addAll(head);
			newHead.add(item);
			List<Integer> remainList=minusList(new ArrayList<Integer>(items),item);
			permutation(newHead,remainList,chooseNum-1);
		}
		
	}

	public static List<Integer> minusList(List<Integer> items,Integer remove){
		List<Integer> remainList=new ArrayList<Integer>();
		for(Integer key:items) {
			if(!key.equals(remove)) {
				remainList.add(key);
			}
		}
		return remainList;
	}

	public  static  <T> List<List<T>> getAllCombination(List<T> items) {
	    List<List<T>> combs=new ArrayList<>();
	    for(int i=1;i<=items.size();i++){
	        combs.addAll(combinationObj(items,i));
	    }
	    return combs;
	}
}