java算法——字符组合排序
发布时间：2010/9/9 10:27:16 来源：城市学习网 编辑：ziteng
题目:用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
不是特别难的题目，暴力算和用图论算（深度遍历）都可以，结果是198.图论的话就是构造无向图，然后深度优先递归。
package com.graphic;
import java.util.Iterator;
import java.util.TreeSet;
public class CharSequence {
private String[] c = {"1","2","2","3","4","5"};
private int n = c.length;
private boolean[] visited = new boolean[n];
private int[][] g = new int[n][n];
private TreeSet<String> ts = new TreeSet<String>();
private String result = "";
public CharSequence(){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i == j) g[i][j] = 0;
else g[i][j] = 1;
}
}
g[3][5] = 0;
g[5][3] = 0;
}
public void depthFirst(int index){
visited[index] = true;
result += c[index];
if(result.length() == n){
ts.add(result);
result = result.substring(0,result.length()-1);
visited[index] = false;
}
else{
for(int i=0; i<n; i++){
if(!visited[i] && g[index][i] == 1){
depthFirst(i);
}else continue;
}
result = result.substring(0,result.length()-1);
visited[index] = false;
}
}
public void graphicGet(){
for(int i=0; i<c.length; i++){
depthFirst(i);
}
int count = 0;
System.out.print("图论的结果：");
Iterator<String> it = ts.iterator();
while(it.hasNext()){
String tmp = it.next();
if(tmp.contains("35")) continue;
if(tmp.contains("53")) continue;
if(tmp.charAt(3) == '4') continue;
System.out.println(tmp);
count++;
}
System.out.println("共计："+count+"个");
}
public void bruteForce(){
System.out.println("暴力搜的结果：");
int count = 0;
for(int i = 122345; i<543222; i++){
String tmp = ""+i;
if(tmp.charAt(3) == '4') continue;
if(tmp.contains("35")) continue;
if(tmp.contains("53")) continue;
if(tmp.contains("5") && tmp.contains("4") && tmp.contains("3") && tmp.contains("1"))
{
int index = tmp.indexOf("2");
if(index == -1) continue;
if(index == tmp.length()-1) continue;
if(tmp.substring(index+1).contains("2")){
System.out.println(tmp);
count++;
}
}
}
System.out.print("共计："+count+"个");
}
public void recrusive(){
}
public static void main(String[] args) {
CharSequence cs = new CharSequence();
//图论的方法
cs.graphicGet();
//暴力搜索
cs.bruteForce();
}
}
