[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 ts = new TreeSet();

  private String result = "";

  public CharSequence(){

  for(int i=0; i

  for(int j=0; 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

  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

  depthFirst(i);

  }

  int count = 0;

  System.out.print("图论的结果:");

  Iterator 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();

  }

  }