全排列算法-遞歸與字典序的實(shí)現(xiàn)方法(Java)

更新時(shí)間：2017年04月10日 09:35:57 投稿：jingxian

下面小編就為大家?guī)?lái)一篇全排列算法-遞歸與字典序的實(shí)現(xiàn)方法(Java) 。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

全排列算法-遞歸與字典序的實(shí)現(xiàn)方法(Java)

全排列：

從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來(lái)，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。
例如：

1 、2 、3三個(gè)元素的全排列為：

{1，2，3}，{1，3，2}，{2，1，3}，{2，3，1}，{3，1，2}，{3，2，1}。

------------------------------------------------------

解法1（遞歸）

如下圖：要對(duì)1、2、3、4進(jìn)行排序，第一個(gè)位置上的元素有四種可能：1或2或3或4，假如已經(jīng)確定了第一個(gè)元素為4，剩下的第二個(gè)位置上可以是1、2、3，很顯然這具有遞歸結(jié)構(gòu)，如果原始要排列的數(shù)組順序?yàn)?、2、3、4，現(xiàn)在只要分別交換1、2，1、3，1、4然后對(duì)剩下的3個(gè)元素進(jìn)行遞歸的排列。

代碼：

-----------------------------------------------

public void Permutation(char chs[],int start )
  {
    if(start==chs.length-1)
    {
      Arrays.toString(chs);
      //如果已經(jīng)到了數(shù)組的最后一個(gè)元素，前面的元素已經(jīng)排好，輸出。
    }
    for(int i=start;i<=chs.length-1;i++)
    {
    //把第一個(gè)元素分別與后面的元素進(jìn)行交換，遞歸的調(diào)用其子數(shù)組進(jìn)行排序
        Swap(chs,i,start);
        Permutation(chs,start+1);
        Swap(chs,i,start);
    //子數(shù)組排序返回后要將第一個(gè)元素交換回來(lái)。 
    //如果不交換回來(lái)會(huì)出錯(cuò)，比如說(shuō)第一次1、2交換，第一個(gè)位置為2，子數(shù)組排序返回后如果不將1、2
    //交換回來(lái)第二次交換的時(shí)候就會(huì)將2、3交換，因此必須將1、2交換使1還是在第一個(gè)位置 
    }
  }
  public void Swap(char chs[],int i,int j)
  {
    char temp;
    temp=chs[i];
    chs[i]=chs[j];
    chs[j]=temp;
  }

遞歸方法會(huì)對(duì)重復(fù)元素進(jìn)行交換比如使用遞歸對(duì){1，1}進(jìn)行全排序會(huì)輸出：{1，1}，{1，1}兩個(gè)重復(fù)的結(jié)果。要在排序的時(shí)候去掉重復(fù)結(jié)果，可以修改一下代碼如下：

public static void Permutation(char chs[],int start)
  {
    if(start==end)
    {
      list.add(new String(chs));
    }
    for(int i=start;i<=chs.length-1;i++)
    {
      if(i==start||chs[i]!=chs[start])
      {
      //在排列的時(shí)候進(jìn)行判斷如果后面的元素與start相同時(shí)就不進(jìn)行排序。
      //這樣就可以避免對(duì)重復(fù)元素進(jìn)行排序
        Swap(chs,i,start);
        Permutation(chs,start+1);
        Swap(chs,i,start);
      }
    }
  }

解法2（字典序法）

字典序法

對(duì)給定的字符集中的字符規(guī)定了一個(gè)先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個(gè)全排列的先后是從左到右逐個(gè)比較對(duì)應(yīng)的字符的先后。

列如：對(duì)a、b、c進(jìn)行排序的結(jié)果是{a,b,c}、{a,c,b}、{b,a,c}、{b,c,a}、{c,a,b}、{c,b,a}

字典序法的優(yōu)點(diǎn)是排列的結(jié)果按照順序輸出并且對(duì)于重復(fù)的元素不進(jìn)行重復(fù)排序。

字典排序法的思想：

例如：對(duì)元素1，2，3，4進(jìn)行排序，假設(shè)默認(rèn)的數(shù)組順序?yàn)閧1，2，3，4}，先輸出第一個(gè)排列：1、2、3、4。然后從右向左找到第一個(gè)非遞增的數(shù)，4，3，因?yàn)?比4小，交換3、4，并且對(duì)3后面的數(shù)進(jìn)行逆序排列，第二個(gè)排列為{1，2，4，3}，再?gòu)挠蚁蜃?，4，2，發(fā)現(xiàn)2比4小，交換從右向左第一個(gè)比2大的數(shù)，交換后{1，3，4，2}再對(duì)3后面的數(shù)進(jìn)行逆序排列第三個(gè)序列為：{1，3，2，4}

依次循環(huán)直到數(shù)組成為完全遞減數(shù)組結(jié)束1、2、3、4字典排序的最大序列為{4，3，2，1}。

--------------------------------------------

代碼

-------------------------------------------

public void PermutationWithDictionary(char chs[])
  {
    Arrays.sort(chs);
    //先對(duì)數(shù)組的元素進(jìn)行依次排序
    while(true)
    {
      System.out.println(chs);
      int j=chs.length-1;
      int index=0;
      for(j=chs.length-2;j>=0;j--)
      {
        if(chs[j]<chs[j+1])
        {
          index=j;
          break;
          //從右向左找到第一個(gè)非遞增的元素
        }
        else if(j==0){
          return;
        }
      }      

      for(j=chs.length-1;j>=0;j--)
      {
        if(chs[j]>chs[index])
          break;
          //從右向左找到第一個(gè)比非遞增元素大的元素
      }
        Swap(chs,index,j);
        //交換找到的兩個(gè)元素
        Reverse(chs,index+1);
        //對(duì)非遞增元素位置后面的數(shù)組進(jìn)行逆序排列
    }    
  }
  public static void Reverse(char chs[],int i)
  {
    int k=i,j=chs.length-1;
    while(k<j)
    {
      Swap(chs,k,j);
      k++;
      j--;
    }
  }

  public static void Swap(char chs[],int i,int j)
  {
    char temp;
    temp=chs[i];
    chs[i]=chs[j];
    chs[j]=temp;
  }

以上這篇全排列算法-遞歸與字典序的實(shí)現(xiàn)方法(Java) 就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: