用Java實現用序數法生成全排列

用java實現用序數法生成全排列:

1. import java.io.*;
2. import java.util.ArrayList;
4. class Arrangement{
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. }
27. private String[] str = null;
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();
40. } catch (IOException e) {
41. e.printStackTrace();
42. }
43. return str;
44. }
46. private void sort(){
47. int num=str.length;
49. int[] n1 = new int[num -1];
50. int[] nss = new int[num];
51. String[] s = new String[num];
53. boolean flag = false;
54. int x = 0;
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. }