前几天看到一个求职面试题,首先要求出一个数组的全排列。但是,全排列以前没有做过,所以想试试。
想了好几天,可是总是想不出来。几天下午吃饭前睡了一会,梦里糊里糊涂地就想了个方法,还有点眉目,于是着手写了一下。
这道题,首先容易想到是用递归来做,想到以前作求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实现字符数组的全排列。 首先,我们需要...
二维数组全排列生成方法,采用递归方法实现,10*24大概用时30min,有待进一步改进
在PHP中,数组全排列是指将数组中的所有元素进行所有可能的排列组合。这通常涉及到回溯算法或者基于比较的排序技巧。以下是对标题和描述中提到的PHP数组全排列方法的详细解释: 首先,我们需要一个包含多个元素的...
本文实例讲述了php求数组全排列,元素所有组合的方法总结。 分享给大家供大家参考,具体如下: <?php $source = array('pll','我','爱','你','嘿'); sort($source); //保证初始数组是有序的 $last = count($...
下面,我们将详细探讨如何使用Objective-C实现全排列算法,并通过数组保存结果。 首先,我们需要定义一个数组来存储原始数据,然后创建一个方法来处理全排列。这个方法将接收两个参数:一是原始数组,二是用于保存...
用c语言实现对一个动态数组的全排列,其中保存生成的全排列用了一个二维指针,求全排列用的递归的方法,代码在vc++6.0下调试通过,并附有详细注释。
在C#编程中,求解数组元素全排列是一项常见的任务,尤其在算法设计和数据处理领域。全排列是指从n个不同元素中取出m个元素,按照一定的顺序排成一列的所有可能组合,其中m≤n。在这个问题中,我们讨论的是如何在C#中...
本文实例讲述了JS实现的数组全排列输出算法。分享给大家供大家参考。具体分析如下: 这段js代码对数组进行全排列输出,改进了一些老的代码 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个...
本文实例讲述了python回溯法实现数组全排列输出的方法。分享给大家供大家参考。具体分析如下: 全排列解释:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个...
本文实例讲述了python标准算法实现数组全排列的方法,代码来自国外网站。分享给大家供大家参考。具体分析如下: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一...
本文实例讲述了C#通过yield实现数组全排列的方法。分享给大家供大家参考。具体分析如下: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的...
本文实例讲述了JavaScript实现数组全排列、去重及求最大值算法。分享给大家供大家参考,具体如下: 1、全排列(递归) function permutation(arr){ if (arr.length == 1) return arr; else if (arr.length == 2)...
在Python编程中,数组全排列是一项常见的算法问题,特别是在数据处理和组合优化中。全排列是指从给定的n个不同元素中取出n个元素的所有可能的排列方式。本篇文章将详细讲解如何利用Python的`yield`关键字来高效地...