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

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

下面小編就為大家?guī)硪黄帕兴惴?遞歸與字典序的實現(xiàn)方法(Java) 。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

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

全排列：

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

1 、2 、3三個元素的全排列為：

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

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

解法1（遞歸）

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

代碼：

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

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

遞歸方法會對重復(fù)元素進(jìn)行交換比如使用遞歸對{1，1}進(jìn)行全排序會輸出：{1，1}，{1，1}兩個重復(fù)的結(jié)果。要在排序的時候去掉重復(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])
      {
      //在排列的時候進(jìn)行判斷如果后面的元素與start相同時就不進(jìn)行排序。
      //這樣就可以避免對重復(fù)元素進(jìn)行排序
        Swap(chs,i,start);
        Permutation(chs,start+1);
        Swap(chs,i,start);
      }
    }
  }

解法2（字典序法）

字典序法

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

列如：對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)點是排列的結(jié)果按照順序輸出并且對于重復(fù)的元素不進(jìn)行重復(fù)排序。

字典排序法的思想：

例如：對元素1，2，3，4進(jìn)行排序，假設(shè)默認(rèn)的數(shù)組順序為{1，2，3，4}，先輸出第一個排列：1、2、3、4。然后從右向左找到第一個非遞增的數(shù)，4，3，因為3比4小，交換3、4，并且對3后面的數(shù)進(jìn)行逆序排列，第二個排列為{1，2，4，3}，再從右向左3，4，2，發(fā)現(xiàn)2比4小，交換從右向左第一個比2大的數(shù)，交換后{1，3，4，2}再對3后面的數(shù)進(jìn)行逆序排列第三個序列為：{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);
    //先對數(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;
          //從右向左找到第一個非遞增的元素
        }
        else if(j==0){
          return;
        }
      }      

      for(j=chs.length-1;j>=0;j--)
      {
        if(chs[j]>chs[index])
          break;
          //從右向左找到第一個比非遞增元素大的元素
      }
        Swap(chs,index,j);
        //交換找到的兩個元素
        Reverse(chs,index+1);
        //對非遞增元素位置后面的數(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;
  }

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

您可能感興趣的文章: