今天在上网时偶然遇到一个算法问题,原文在这里:
http://blog.csdn.net/mdj_bj/article/details/7792223。
题目是用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。
看了题后没看答案直接开始动工,本来就是一个比较简单的全排列问题,算法自己也立即想了出来,就是不断在排列好的序列中插入新的元素。可貌似自己很久没写过这些算法题了,具体实现起来竟然花了好长时间,中间几次明明知道思路可就是不知道怎么转化为代码
。不过还好最后终于搞定,有了如下代码:
package com.tc.test;
import java.util.Arrays;
public class MTest {
private char list[] = new char[]{'1', '2', '2', '3', '4', '5'};
private int total = list.length;
public static void main(String[] args) {
long l1 = System.currentTimeMillis();
new MTest().test();
long l2 = System.currentTimeMillis();
System.out.println("time:" + (l2 - l1) + "ms");
}
private void test() {
printInOrder(new char[list.length], 0);
}
private void printInOrder(char[] current, int fill) {
if (fill == total) {
print(current);
return;
}
char a = list[fill];
for (int i = 0; i < total; i++) {
if (current[i] == 0) {
char[] tmp = Arrays.copyOf(current, total);
tmp[i] = a;
printInOrder(tmp, fill + 1);
}
}
}
private void print(char[] array) {
String line = new String(array);
if (line.charAt(2) == '4' || line.indexOf("35") != -1 ||
line.indexOf("53") != -1) {
return;
}
System.out.println(line);
}
}
弄完自以为大功告成,和原文里的算法做了一下对比,结果发现上面算法的结果比原文中的结果数量多了一倍,仔细一想,原来忽略了两个2造成的影响,可是木已成舟,想不出方法从根源解决,只能在最后过滤一下了,于是乎,最终的成品变成了下面这个样子:
package com.tc.test;
import java.util.Arrays;
import java.util.BitSet;
public class MTest {
private char list[] = new char[]{'1', '2', '2', '3', '4', '5'};
private int total = list.length;
private BitSet state = new BitSet(543222);
public static void main(String[] args) {
long l1 = System.currentTimeMillis();
new MTest().test();
long l2 = System.currentTimeMillis();
System.out.println("time:" + (l2 - l1) + "ms");
}
private void test() {
printInOrder(new char[list.length], 0);
}
private void printInOrder(char[] current, int fill) {
if (fill == total) {
print(current);
return;
}
char a = list[fill];
for (int i = 0; i < total; i++) {
if (current[i] == 0) {
char[] tmp = Arrays.copyOf(current, total);
tmp[i] = a;
printInOrder(tmp, fill + 1);
}
}
}
private void print(char[] array) {
String line = new String(array);
int n = Integer.parseInt(line);
if (state.get(n)) {
return;
}
state.set(n);
if (line.charAt(2) == '4' || line.indexOf("35") != -1
|| line.indexOf("53") != -1) {
return;
}
System.out.println(line);
}
}
和原文中的算法重新对比,完全一致,而且性能上还有20%左右的提升,不过缺点是要开一个近100K的BitSet。
分享到:
相关推荐
使用递归实现的全排列算法,输出所有的全排列。 各种主流程序设计语言实现!
全排列算法
JAVA递归实现全排列算法,含实现源代码,如a、b、c、d的全排列为: abcd abdc acbd acdb adcb adbc bacd badc bcad bcda bdca bdac cbad cbda cabd cadb cdab cdba dbca dbac dcba dcab dacb dabc
全排列算法: 比如字符串abc,全排列结果为abc,acb,bac,bca,cba,cab。
利用中介数实现全排列算法,采用java实现。
主要介绍了Java实现字符数组全排列的方法,涉及Java针对字符数组的遍历及排序算法的实现技巧,需要的朋友可以参考下
组合数学中六种全排列算法详细解析,对于自学很有帮助哦,这里没有代码。
java 递归,abcd全排列,非常简单的。
Java 全排列算法实现,网上搜的,然后整理了一下。呵呵`````
全排列-非递归算法(适合动态的新元素加入重新输出全排列-本程序以1到6的数字输出为例)
java算法分析与设计之全排列问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,尤其...
给出了字典排序求取全排列的算法实现,JAVA
主要介绍了JAVA用递归实现全排列算法的相关资料,文中示例代码非常详细,帮助大家更好的理解和学习,感兴趣的朋友可以了解下
java回溯算法调试
题目描述:给定一个数列a1,a2,a3…an,输出他所有的全排列。 算法设计描述: 1、获取当前的一种排列,用start,end分别表示该排列的列头,列尾; 2、判断start是否和end相等,若相等,执行3,否则执行4; 3、将当前...
主要介绍了Java基于递归解决全排列问题算法,结合实例形式分析了Java使用递归算法解决全排列问题的原理与具体实现技巧,需要的朋友可以参考下
下面小编就为大家带来一篇全排列算法-递归与字典序的实现方法(Java) 。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
今天小编就为大家分享一篇关于Java全排列字典序下的下一个排列,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
计算机算法设计与实现的实验一 本人觉得它是对递归与分治策略思想最好理解的例子!
用java语言编写的两种方法求全排列的程序,输入数字的长度可以输出所有的数字全排列