Problem24

package com.yao.Algorithms;

import java.util.ArrayList;
import java.util.List;
/**
 * 
 * @author shuimuqinghua77 @date 2012-4-26下午02:01:16
 *
 */
public class Problem24 {
/**
 * 存放数字
 */
private static List<Integer> list=new ArrayList<Integer>();

private static int MILLION=100*100*100;
private static int count=0;
private static StringBuilder millionth=new StringBuilder();
public static void main(String[] args) {
	for(int i=0;i<10;i++)
		list.add(i);
	find(factor(list.size()-1),millionth);
	System.out.println(millionth);
	System.out.println(count);
}
/**
 * 表示一个全排列的量
 * @param size
 * @return
 */
private static int factor(int size) {
	int factor=1;
	for(int i=1;i<=size;i++){
		factor*=i;
	}
	return factor;
}
/**
 * 以递归的方式遍历
 * @param factor
 * @param millionth
 * @return
 */
private static int find(int factor,StringBuilder millionth) {
	for(int j=0;j<list.size();j++)
	{
		int future=count+factor;
		if(future<MILLION){
			count=future;
		}
		else if(future>MILLION){
			millionth.append(list.get(j));
			list.remove(j);
			return find(factor(list.size()-1),millionth);
		}
		else{
			millionth.append(list.get(j));
			list.remove(j);
			/**
			 * 关键部分   剩下的数字应该以倒序添加到digit末尾，也就是从大到小的顺序
			 */
			for(int k=list.size()-1;k>=0;k--)
				millionth.append(list.get(k));
			return future;
		}
	}
	return count;
}
}