思想比知识更重要 成长比成功更重要
回归blogjava
posts - 73,  comments - 55,  trackbacks - 0
java字符串全排列问题（经典）
/*
 * 原题如下：用1、2、2、3、4、6这六个数字，用java写一个main函数，打印出所有不同的排列，
 * 如：612234、412346等，要求："4"不能在第三位，"3"与"6"不能相连. 
 * 
 * 1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，
 * 所有结点的遍历路径就是最后对这6个数字的排列组合结果集。 
 * 2 显然这个结果集还未达到题目的要求。从以下几个方面考虑： 
 * 1. 3，6不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。 
 * 2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果 
 * 3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。
  */

import  java.util.Iterator;
 import  java.util.TreeSet;

 public   class  Test  {

  private  String[] b  =   new  String[]  {  " 1 " ,  " 2 " ,  " 2 " ,  " 3 " ,  " 4 " ,  " 6 "  } ;

  private   int  n  =  b.length;

  private   boolean [] visited  =   new   boolean [n];

  private   int [][] a  =   new   int [n][n];

  private  String result  =   "" ;

  private  TreeSet set  =   new  TreeSet();

  public   static   void  main(String[] args)  {
   new  Test().start();
 }

  private   void  start()  {

   //  Initial the map a[][]
   for  ( int  i  =   0 ; i  <  n; i ++ )  {
    for  ( int  j  =   0 ; j  <  n; j ++ )  {
     if  (i  ==  j)  {
     a[i][j]  =   0 ;
    }   else   {
     a[i][j]  =   1 ;
    }
   }
  }

   //  3 and 5 can not be the neighbor.
  a[ 3 ][ 5 ]  =   0 ;
  a[ 5 ][ 3 ]  =   0 ;

   //  Begin to depth search.
   for  ( int  i  =   0 ; i  <  n; i ++ )  {
    this .depthFirstSearch(i);
  }

   //  Print result treeset.
  Iterator it  =  set.iterator();
   while  (it.hasNext())  {
   String string  =  (String) it.next();
   System.out.println(string);
  }
 }

  private   void  depthFirstSearch( int  startIndex)  {
  visited[startIndex]  =   true ;
  result  =  result  +  b[startIndex];
   if  (result.length()  ==  n)  {
 //    "4" can not be the third position.
    if  (result.indexOf( " 4 " )  !=   2 )  {
 //     Filt the duplicate value.
    set.add(result);
   }
  }
   for  ( int  j  =   0 ; j  <  n; j ++ )  {
    if  (a[startIndex][j]  ==   1   &&  visited[j]  ==   false )  {
    depthFirstSearch(j);
   }
  }

   //  restore the result value and visited value after listing a node.
  result  =  result.substring( 0 , result.length()  -   1 );
  visited[startIndex]  =   false ;
 }
}

只要这样定义图，根本不用在代码中写IF ELSE语句。
实际上基于图的算法好处在于，只要你能定义好满足题目要求的图结构，遍历的结果就是你要的结果，不用任何对遍历结果做任何处理。包括本题中的：4不能在第三位置，3，5不能相连，唯一性要求，其实都可以在体现在构造的图形结构里，然后直接遍历图取得自己要的结果。而不用再次处理结果集。只是说这里实际上对其它要求要体现在图结构里有困难（理论上是可以的），但起码3，5不能相接是很好构造的，就是上面的代码段来解释的。

关于图形数据结构建议先看看数据结构的书，主要是将如何利用二维数组描述图结构，再看看图的深度遍历实现原理。最后再应用到这个问题上来，自然就不难明白了。

posted on 2007-03-02 17:37 保尔任 阅读(2370) 评论(0)  编辑  收藏 所属分类: Arithmetic & Data Structure

只有注册用户登录后才能发表评论。
网站导航:
 

<2007年3月>
日一二三四五六
25262728123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(4)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Copyright ©2024 保尔任 Powered By博客园 模板提供：沪江博客