用Java实现用序数法生成全排列

用Java实现用序数法生成全排列

用java实现用序数法生成全排列:

1. import java.io.*;  
2. import java.util.ArrayList;  
3.   
4. class Arrangement{  
5.       
6.     public static void main(String args[]){  
7.         Arrangement arrangement = null;  
8.         int num = 0;//要排序的个数   
9.         boolean flag = true;//标志位，如果用户输入的待排序个数不合法，该值一直为true   
10.         ArrayList<String> strs = new ArrayList<String>();  
11.         while(flag){  
12.             try{  
13.                 num = Integer.parseInt(readDataFromConsole("请输入待排序的个数："));  
14.                 flag = false;  
15.             }catch(Exception e){  
16.                 System.out.println("请输入整数.");  
17.             }  
18.         }  
19.         for(int i = 1; i <= num; i ++){  
20.             strs.add(readDataFromConsole("请输入第" + i + "个字符: "));   
21.         }  
22.         arrangement = new Arrangement(strs.toArray(new String[]{}));  
23.         System.out.println("排列后的数据为：");  
24.         arrangement.sort();  
25.     }  
26.       
27.     private String[] str = null;  
28.       
29.     public Arrangement(String[] s){  
30.         this.str = s;  
31.     }  
32.     //从控制台读入数据   
33.     private static String readDataFromConsole(String prompt) {  
34.             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
35.             String str = null;  
36.             try {  
37.                     System.out.print(prompt);  
38.                     str = br.readLine();  
39.   
40.             } catch (IOException e) {  
41.                     e.printStackTrace();  
42.             }  
43.             return str;  
44.         }  
45.       
46.     private void sort(){  
47.         int num=str.length;  
48.           
49.         int[] n1 = new int[num -1];  
50.         int[] nss = new int[num];  
51.         String[] s = new String[num];  
52.           
53.         boolean flag = false;  
54.         int x = 0;  
55.           
56.         do{  
57.             if(x == 0){//第一遍初始化   
58.                 for(int i = 0;i < num - 1;i ++){  
59.                     n1[i] = 0;  
60.                 }  
61.             } else {//生成序数   
62.                 for(int i = 0;i < num - 1;i ++){  
63.                     if(n1[num - 2 - i] < i + 1){  
64.                         n1[num - 2 - i] ++;  
65.                         for(int j=num-1-i;j<num-1;j++){  
66.                             n1[j] = 0;  
67.                         }  
68.                         break;  
69.                     }  
70.                 }  
71.             }  
72.             for(int i = 0;i < num - 1;i++){  
73.                 if(n1[i] == (num - 1 - i)){  
74.                     flag = false;  
75.                 } else {  
76.                     flag = true;  
77.                     break;  
78.                 }  
79.             }  
80.             for(int i = 0;i < num;i++){//标记位赋初值   
81.                 nss[i] = 0;  
82.             }  
83.             for(int i = 0;i < num - 1;i++){//计算排列顺序并为排列后的赋值   
84.                 int hh = 0, j = 0;//记录前边总共移动的位数   
85.                 do{  
86.                     if(nss[num - 1 - hh] == 1){  
87.                         hh++;  
88.                         continue;  
89.                     } else {  
90.                         if(j == n1[i]){  
91.                             break;//每个字母距最右端未填入的位置   
92.                         } else {  
93.                             hh++;  
94.                             j++;  
95.                         }  
96.                     }  
97.                 } while(true);  
98.                 hh = num - 1 - hh;  
99.                 s[hh] = str[num-1-i];  
100.                 nss[hh] = 1;  
101.             }  
102.             for(int i = 0; i < num;i++){//查找空缺位   
103.                 if(nss[i] == 0) {  
104.                     s[i] = str[0];  
105.                     break;  
106.                 }  
107.             }  
108.             System.out.print(++x + "\t");  
109.             for(int i = 0;i < num - 1;i++){  
110.                 System.out.print(n1[i] + "");  
111.             }  
112.             System.out.print("\t");  
113.             for(int i = 0;i < num;i++){  
114.                 System.out.print(s[i] + "");  
115.             }  
116.             System.out.println();  
117.         }while(flag);  
118.     }  
119. }