Java全排列算法字典序下的下一個(gè)排列講解

一直寫過(guò)數(shù)組全排列的算法，當(dāng)時(shí)接觸的是使用回溯的方法，這樣可以保證生成的全排列一定是按照字典序的，但是今天在做leetcode上的一道題時(shí)，問(wèn)題是要你找到某個(gè)排列情況的下一個(gè)按照字典序排列的狀態(tài)。

如果直接一點(diǎn)，大可從頭開(kāi)始做全排列，然后到目標(biāo)狀態(tài)時(shí)，在做一次即可找到要的狀態(tài)，但是如果題目給的狀態(tài)非?？亢?，則要花費(fèi)很大的代價(jià)，這樣做就顯得有些笨拙了。

所以做這道題的時(shí)候一直在思考如何按照字典序生成全排列。

假設(shè)此時(shí)給出的狀態(tài)時(shí)5 2 4 3 1，那么下一個(gè)狀態(tài)要如何確定呢？首先從人的視角來(lái)看，絕對(duì)會(huì)從序列末尾向前開(kāi)始查找，例如如果給的狀態(tài)時(shí)1 2 3 4 5，則很容易發(fā)現(xiàn)下一個(gè)狀態(tài)應(yīng)該是1 2 3 5 4，這樣就給出了一個(gè)策略，第一步應(yīng)該先找從末尾開(kāi)始向前第一對(duì)非逆序數(shù)對(duì)，這當(dāng)然有理由，因?yàn)槿绻悄嫘虻?，說(shuō)明該種情況一定是已經(jīng)進(jìn)行過(guò)交換了，則絕對(duì)不會(huì)是下一種情況交換的候選位置，因此會(huì)發(fā)現(xiàn)5 2 4 3 1中第一個(gè)非逆序數(shù)對(duì)是2 4，所以交換的候選對(duì)象應(yīng)該是2（2是較小的那一個(gè)）；緊接著繼續(xù)思考，應(yīng)該和后面的哪一個(gè)進(jìn)行交換。首先顯而易見(jiàn)的是，2后面的子序列一定是逆序的。那么如果要和2交換并且使結(jié)果是字典序的下一個(gè)的話，那么與2交換的一定是2后面的比2大的最小的哪一個(gè)數(shù)，因此第二步就是從序列末尾開(kāi)始向前查找第一個(gè)比2大的數(shù)，與2進(jìn)行交換（此時(shí)為 5 3 4 2 1），那么下一步也是顯而易見(jiàn)的，3后面的序列應(yīng)該是由5 3開(kāi)始的字典序最小的一個(gè)序列，因此要將3后面的序列逆置。最后得到答案5 3 1 2 4。

過(guò)程并不復(fù)雜，思路和人思考的順序應(yīng)該是一樣的，直接上coding了。

public void reverse(int []nums,int l,int r){
    while(l<r){
      int tmp=nums[l];
      nums[l]=nums[r];
      nums[r]=tmp;
      l++;
      r--;
    }
  }
  public void nextPermutation(int[] nums) {
    if(nums.length==0||nums.length==1) return;
    int i=nums.length-1;
    for(;i>=1;i--){
      if(nums[i]>nums[i-1])
        break;
    }
    if(i==0){
      Arrays.sort(nums);
      return;
    }
    int index=i-1;
    int diff=nums[i-1];
    for(i=nums.length-1;i>=0;i--){
      if(nums[i]>diff)
        break;
    }
    int tmp=nums[index];
    nums[index]=nums[i];
    nums[i]=tmp;
    reverse(nums,index+1,nums.length-1);
  }

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)億速云的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接