用Java實現換位法生成全排列

用Java實現換位法生成全排列：

1. import java.util.ArrayList;
2. import java.io.*;
4. //換位法生成全排列
5. class ReplaceArrangement{
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();
15. } catch (IOException e) {
16. e.printStackTrace();
17. }
18. return str;
19. }
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("----第一個排列必須有序------");
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. }