数组的全排列（1）

前几天看到一个求职面试题，首先要求出一个数组的全排列。但是，全排列以前没有做过，所以想试试。

想了好几天，可是总是想不出来。几天下午吃饭前睡了一会，梦里糊里糊涂地就想了个方法，还有点眉目，于是着手写了一下。

这道题，首先容易想到是用递归来做，想到以前作求n!的代码，但是这里与以前不同，因为求n!在迭代是返回一个值，但是我们这里返回是数组，而且每次返回的数组的维数不一样。其实解决的方法很简单，就是用返回值迭代，把需要迭代的对象做成一个函数的参数，同时它是全局变量，就可以在迭代中改变值了。

另外值得注意的是，因为java是引用传值，所以要把对象做成类，用它的属性的值迭代，并定义类中改变属性的get和set方法。

编程的时候出了不少错，都是手误，hh，所以感觉一点点测试并写下来反而比较快。


代码在下面：
首先是用来迭代的类 MyString.class

package testing_1.perm;

public class MyString {
private String[] strs;
public MyString() {
strs=null;
}
public MyString(final int n){
strs=new String[n];
}


public void setStrs(String[] strs) {
this.strs = strs;
}

public String[] getStrs() {
return strs;
}

public void sort(){
// sort ascending
for(int i=0;i<strs.length-1;i++){
for(int j=0;j<strs.length-i-1;j++){
if (strs[j].compareToIgnoreCase(strs[j+1]) > 0) {
String tem = strs[j];
strs[j] = strs[j + 1];
strs[j + 1] = tem;
}
}
}

}
}

迭代的主程序，主要方法是permutation

package testing_1.perm;
public class perm {
public perm() {
}

public static void main(String[] args) {
MyString mystr=new MyString();
long time=System.currentTimeMillis();
String str="12345";
permutation(str,mystr,str.length());
mystr.sort();
for(int i=0;i<mystr.getStrs().length;i++){
System.out.println((i+1)+":"+mystr.getStrs()[i]);
}
System.out.println("TIME
PASSED:"+(System.currentTimeMillis()
-time)+"ms");


}

public static String insert(char ch, String str, int i) {
if (i < 0||i>str.length()) {
System.out.println("insert: i=" + i + "invalid");
return null;
}
String temp1 = str.substring(0, i);
String temp2 = str.substring(i);
return temp1 + ch + temp2;
}


public static void produce(char ch,MyString mystr){
int k=0;
String[] temp1=mystr.getStrs();
final int len=temp1.length;
final int lem=temp1[0].length();
String[] temp2=new String[len*(lem+1)];
for(int i=0;i<len;i++){
for(int j=0;j<lem+1;j++){
temp2[k]=insert(ch,temp1[i],j);
k++;
}
}
mystr.setStrs(temp2);
}



public static int permutation(String str,MyString mystr,int n){
if(n<1){
System.out.println("permutation: n="+n+" invalid");
return -1;//abnormal
}
if(n>1){
permutation(str,mystr,n-1);
char a=str.charAt(n-1);
produce(a,mystr);
n--;
return 0;//n>1
}else if(n==1){
char a=str.charAt(0);
String strs[]={""+a};
mystr.setStrs(strs);
return 1;//n==1
}
return -2;
}



}

在JBuilder2006上测试通过，结果如下

1:12345
2:12354
3:12435
4:12453
5:12534
6:12543
7:13245
8:13254
9:13425
10:13452
11:13524
12:13542
13:14235
14:14253
15:14325
16:14352
17:14523
18:14532
19:15234
20:15243
21:15324
22:15342
23:15423
24:15432
25:21345
26:21354
27:21435
28:21453
29:21534
30:21543
31:23145
32:23154
33:23415
34:23451
35:23514
36:23541
37:24135
38:24153
39:24315
40:24351
41:24513
42:24531
43:25134
44:25143
45:25314
46:25341
47:25413
48:25431
49:31245
50:31254
51:31425
52:31452
53:31524
54:31542
55:32145
56:32154
57:32415
58:32451
59:32514
60:32541
61:34125
62:34152
63:34215
64:34251
65:34512
66:34521
67:35124
68:35142
69:35214
70:35241
71:35412
72:35421
73:41235
74:41253
75:41325
76:41352
77:41523
78:41532
79:42135
80:42153
81:42315
82:42351
83:42513
84:42531
85:43125
86:43152
87:43215
88:43251
89:43512
90:43521
91:45123
92:45132
93:45213
94:45231
95:45312
96:45321
97:51234
98:51243
99:51324
100:51342
101:51423
102:51432
103:52134
104:52143
105:52314
106:52341
107:52413
108:52431
109:53124
110:53142
111:53214
112:53241
113:53412
114:53421
115:54123
116:54132
117:54213
118:54231
119:54312
120:54321
TIME PASSED:78ms