用Java实现换位法生成全排列

用Java实现换位法生成全排列

用Java实现换位法生成全排列：

1. import java.util.ArrayList;  
2. import java.io.*;  
3.   
4. //换位法生成全排列   
5. class ReplaceArrangement{  
6.   
7.     //从控制台读入数据   
8.     private static String readDataFromConsole(String prompt) {  
9.             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
10.             String str = null;  
11.             try {  
12.                     System.out.print(prompt);  
13.                     str = br.readLine();  
14.   
15.             } catch (IOException e) {  
16.                     e.printStackTrace();  
17.             }  
18.             return str;  
19.         }  
20.       
21.     public static void main(String args[]){  
22.         class Node{  
23.             int value = 0;// 元素值   
24.             int dir = -1;// 0 : 左向箭头，1：有向箭头   
25.         }  
26.         System.out.println("------换位法求全排列---------");  
27.         System.out.println("----第一个排列必须有序------");  
28.           
29.         int n = 0;//元素个数   
30.         boolean flag = true;//从控制台读入数据不合法的话，该值一直为true   
31.         while(flag){  
32.             try{  
33.                 n = Integer.parseInt(readDataFromConsole("请输入待排序元素个数: "));  
34.                 flag = false;  
35.             }catch(Exception e){  
36.                 System.out.println("请输入整数.");  
37.             }     
38.         }  
39.         flag = true;  
40.         ArrayList<Node> nodes = new ArrayList<Node>(n);  
41.         Node node = null;  
42.         for(int i = 1;i <= n;i++){//排列初始化   
43.             node =  new Node();  
44.             while(flag){  
45.                 try{  
46.                     node.value = Integer.parseInt(readDataFromConsole("请输入第" + i + "个元素的值: "));  
47.                     flag = false;  
48.                 }catch(Exception e){  
49.                     System.out.println("请输入整数.");  
50.                 }  
51.             }  
52.             flag = true;  
53.             node.dir = 0;  
54.             nodes.add(node);  
55.             node = null;  
56.         }  
57.         for(int i = 0;i < n;i++){  
58.             System.out.print(nodes.get(i).value + "\t");  
59.         }  
60.         System.out.println();  
61.         int count = 1;  
62.         while(true){  
63.             int j = 0; // 记录最大活动整数下标   
64.             int Max = 0;  
65.             for(int i = 0;i < n;i++){ // 找出最大活动整数   
66.                 if(0 == i && 0 == nodes.get(i).dir){  
67.                     Max = Max;  
68.                 }else if(n-1 == i && 1 == nodes.get(i).dir){ /// 此处应该是一次空操作，不可以轻易将Max 置为 0 ********   
69.                     Max = Max;  
70.                 }else if(0 == nodes.get(i).dir && i>0 && nodes.get(i).value>nodes.get(i - 1).value && nodes.get(i).value>Max){  
71.                     Max = nodes.get(i).value;  
72.                     j = i;  
73.                 }else if(1 == nodes.get(i).dir && i<n-1 && nodes.get(i).value>nodes.get(i + 1).value && nodes.get(i).value > Max){  
74.                     Max = nodes.get(i).value;  
75.                     j = i;  
76.                 }             
77.             }  
78.             //cout << endl;   
79.             //cout << j << " " << Max << endl;   
80.             if( 0 == Max ) // 没有活动整数   
81.                 break;  
82.             if( 0 == nodes.get(j).dir)  // 交换最大整数与其相邻的数及方向   
83.             {  
84.                 int temp,dirtemp;  
85.                 temp =nodes.get(j).value;  
86.                 dirtemp=nodes.get(j).dir;  
87.                 nodes.get(j).value=nodes.get(j - 1).value;  
88.                 nodes.get(j).dir=nodes.get(j - 1).dir;  
89.                 nodes.get(j - 1).value=temp;  
90.                 nodes.get(j - 1).dir=dirtemp;  
91.             }  
92.             else if( 1 == nodes.get(j).dir)  
93.             {  
94.                 int temp,dirtemp;  
95.                 temp =nodes.get(j).value;  
96.                 dirtemp=nodes.get(j).dir;  
97.                 nodes.get(j).value=nodes.get(j + 1).value;  
98.                 nodes.get(j).dir=nodes.get(j + 1).dir;  
99.                 nodes.get(j + 1).value=temp;  
100.                 nodes.get(j + 1).dir=dirtemp;  
101.             }  
102.             for(int i=0;i<n;i++)//变换比最大活动整数大的数的方向   
103.             {  
104.                 if(nodes.get(i).value>Max)  
105.                 {  
106.                     if(0 == nodes.get(i).dir){  
107.                         nodes.get(i).dir=1;  
108.                     }else if(1 == nodes.get(i).dir){  
109.                         nodes.get(i).dir=0;  
110.                     }  
111.                 }  
112.             }  
113.             for(int i=0;i<n;i++){  
114.                 System.out.print(nodes.get(i).value + "\t");  
115.             }  
116.             count++;  
117.             System.out.println();  
118.         }  
119.         System.out.println("排列总数为：" + count);  
120.     }  
121. }