`
whoami0508
  • 浏览: 8599 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

数组的全排列(1)

    博客分类:
  • java
阅读更多

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

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

这道题,首先容易想到是用递归来做,想到以前作求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
分享到:
评论

相关推荐

    Java实现字符数组全排列的方法

    全排列是指从给定的字符数组中,按照一定的顺序生成所有可能的排列组合。这个问题通常使用回溯法来解决,因为它能够有效地避免重复的排列。下面我们将深入探讨如何使用Java实现字符数组的全排列。 首先,我们需要...

    二维数组全排列代码C++版

    二维数组全排列生成方法,采用递归方法实现,10*24大概用时30min,有待进一步改进

    php求数组全排列,元素所有组合的方法

    在PHP中,数组全排列是指将数组中的所有元素进行所有可能的排列组合。这通常涉及到回溯算法或者基于比较的排序技巧。以下是对标题和描述中提到的PHP数组全排列方法的详细解释: 首先,我们需要一个包含多个元素的...

    php求数组全排列,元素所有组合的方法总结

    本文实例讲述了php求数组全排列,元素所有组合的方法总结。 分享给大家供大家参考,具体如下: &lt;?php $source = array('pll','我','爱','你','嘿'); sort($source); //保证初始数组是有序的 $last = count($...

    objective-c数组全排列算法

    下面,我们将详细探讨如何使用Objective-C实现全排列算法,并通过数组保存结果。 首先,我们需要定义一个数组来存储原始数据,然后创建一个方法来处理全排列。这个方法将接收两个参数:一是原始数组,二是用于保存...

    求一个动态数组的全排列,c语言实现

    用c语言实现对一个动态数组的全排列,其中保存生成的全排列用了一个二维指针,求全排列用的递归的方法,代码在vc++6.0下调试通过,并附有详细注释。

    C#求数组中元素全排列的方法

    在C#编程中,求解数组元素全排列是一项常见的任务,尤其在算法设计和数据处理领域。全排列是指从n个不同元素中取出m个元素,按照一定的顺序排成一列的所有可能组合,其中m≤n。在这个问题中,我们讨论的是如何在C#中...

    JS实现的数组全排列输出算法

    本文实例讲述了JS实现的数组全排列输出算法。分享给大家供大家参考。具体分析如下: 这段js代码对数组进行全排列输出,改进了一些老的代码 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个...

    python回溯法实现数组全排列输出实例分析

    本文实例讲述了python回溯法实现数组全排列输出的方法。分享给大家供大家参考。具体分析如下: 全排列解释:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个...

    python标准算法实现数组全排列的方法

    本文实例讲述了python标准算法实现数组全排列的方法,代码来自国外网站。分享给大家供大家参考。具体分析如下: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一...

    C#通过yield实现数组全排列的方法

    本文实例讲述了C#通过yield实现数组全排列的方法。分享给大家供大家参考。具体分析如下: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的...

    JavaScript实现数组全排列、去重及求最大值算法示例

    本文实例讲述了JavaScript实现数组全排列、去重及求最大值算法。分享给大家供大家参考,具体如下: 1、全排列(递归) function permutation(arr){ if (arr.length == 1) return arr; else if (arr.length == 2)...

    python通过yield实现数组全排列的方法

    在Python编程中,数组全排列是一项常见的算法问题,特别是在数据处理和组合优化中。全排列是指从给定的n个不同元素中取出n个元素的所有可能的排列方式。本篇文章将详细讲解如何利用Python的`yield`关键字来高效地...

Global site tag (gtag.js) - Google Analytics