[Java算法]字符组合排序实例

题目:用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_[j] = 0;_

　　else g[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_&& g[index]== 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();

　　}

　　}