Problem24

1.package com.yao.Algorithms;
2.
3.import java.util.ArrayList;
4.import java.util.List;
5./**
6. *
7. * @author shuimuqinghua77 @date 2012-4-26下午02:01:16
8. *
9. */
10.public class Problem24 {
11./**
12. * 存放数字
13. */
14.private static List<Integer> list=new ArrayList<Integer>();
15.
16.private static int MILLION=100*100*100;
17.private static int count=0;
18.private static StringBuilder millionth=new StringBuilder();
19.public static void main(String[] args) {
20.    for(int i=0;i<10;i++)
21.        list.add(i);
22.    find(factor(list.size()-1),millionth);
23.    System.out.println(millionth);
24.    System.out.println(count);
25.}
26./**
27. * 表示一个全排列的量
28. * @param size
29. * @return
30. */
31.private static int factor(int size) {
32.    int factor=1;
33.    for(int i=1;i<=size;i++){
34.        factor*=i;
35.    }
36.    return factor;
37.}
38./**
39. * 以递归的方式遍历
40. * @param factor
41. * @param millionth
42. * @return
43. */
44.private static int find(int factor,StringBuilder millionth) {
45.    for(int j=0;j<list.size();j++)
46.    {
47.        int future=count+factor;
48.        if(future<MILLION){
49.            count=future;
50.        }
51.        else if(future>MILLION){
52.            millionth.append(list.get(j));
53.            list.remove(j);
54.            return find(factor(list.size()-1),millionth);
55.        }
56.        else{
57.            millionth.append(list.get(j));
58.            list.remove(j);
59.            /**
60.             * 关键部分   剩下的数字应该以倒序添加到digit末尾，也就是从大到小的顺序
61.             */
62.            for(int k=list.size()-1;k>=0;k--)
63.                millionth.append(list.get(k));
64.            return future;
65.        }
66.    }
67.    return count;
68.}
69.}