關于排列問題的一系列歸類

2019-11-14 15:08:44

字體：大中小

來源：轉載

供稿：網友

最近在做leetcode的時候，做到了一些排列的問題，比如Next Permutation（求已知當前排列的下一個全排列），Permutations（給定一個整型集合，求全排列），Permutations II（與Permutations類似，只是增加了重復元素出現的情況），Permutation Sequence（給定數字1...n，求這n個數的全排列的第k項）。稍微整理了下方法，下面進行解釋：

首先，當然排列問題是算法里的經典問題了，通常給定n個元素，要求這n個元素的全排列，我們一般采用的是遞歸的方法，引入集合R（i）的概念，R（i）表示原集合R出去第i項之后的集合。集合X的全排列，我們記為perm（X）。(r)perm(X)表示在全排列perm（X）的每一個排列前面加上前綴r所得到的排列。因此，我們可以很容易就得到perm（R）的歸納定義：

perm（R）=（r），當n=1，其中r是R中的唯一元素。當n>1時，perm（R）由(r1)perm(R1),(r2)perm(R2),.....(rn)perm(Rn)構成，r1,r2....rn構成集合R。

由以上定義能很容易的寫出此遞歸算法，這是解Permutations問題的一種思路。當然還有其他方法，在介紹之前，我們先講講Next Permutation這個題。這個題還是比較有意思的，它已經給定了一個排列，要求找出下一個，比如1,2,3 它的下一個排列即為1,3,2。通過寫一兩個全排列我們不難觀察出，當前排列的下一個排列即為比當前排列大的下一個數，當然這個數是有要求的，即每一位都只能用集合中的數，且每個數只能用一次。這個很好懂，比如21354這個數，可以看成是集合{1,2,3，4,5}的一個排列，它的下一個排列應該是比21354大的第一個數21435。但是怎么找到這個數呢？我們觀察可以看到，在21354這個排列中，顯然54，已經是以213為前綴的最大的數了，所以以213為前綴，不可能具有更大的排列，所以接下來考慮以21為前綴的排列，此時問題簡化為找354的下一個排列，既然213為前綴的排列沒有了，那自然會想到找下一個比3大的數，接著21為前綴，產生此前綴下的最小排列。我們從右邊開始往左邊找，找到第一個比3大的數，此時為4，交換3和4的位置，此時前綴為214，剩下兩個數5,3。以214為前綴的最小排列即為21435。那么在程序中怎么實現？只需對當前排列，從右往左依次比較相鄰的兩個數，直到找到前一個數比后一個數小的情況。此時記錄前一個數的位置及數值，再從后往前找第一個比這個數大的數，交換他們的位置，產生新的前綴，然后對剩下的數字，利用sort函數，產生最小的后綴，此時的排列即為所求。

public void nextPermutation(int[] nums) {     int Loc=nums.length-1;     int Loc1=0;     for(int i=Loc-1;i>=0;i--){         if(nums[i]<nums[i+1]) {Loc=i;break;}                     }      if(Loc!=nums.length-1){         for(int i=nums.length-1;i>Loc;i--){              if(nums[i]>nums[Loc]) {Loc1=i;break;}         }        int a=nums[Loc1];        nums[Loc1]=nums[Loc];        nums[Loc]=a;        if(Loc!=nums.length-2){            int[] inter=new int[nums.length-Loc-1];            for(int i=Loc+1;i<nums.length;i++)inter[nums.length-i-1]=nums[i];            Arrays.sort(inter);            for(int i=Loc+1;i<nums.length;i++)nums[i]=inter[i-Loc-1];         }     }    else Arrays.sort(nums);            //return nums;}

介紹了Next Permutatio的方法，下面我們可以很容易將這個方法用在Permutations這個題目上，首先我們隊集合里的元素進行sort產生第一個排列，然后調用Next Permutatio，不斷產生新的排列，leetcode上這種方法親測可行。

public List<List<Integer>> permute(int[] nums) {     List<List<Integer>> out=new ArrayList<List<Integer>>();       if(nums.length==0)return out;     Arrays.sort(nums);     boolean c=true;     while(c){	List<Integer>inter=new ArrayList<Integer>();	for(int i=0;i<nums.length;i++){	   inter.add(nums[i]);	}	out.add(inter);	int count=0;	for(int i=0;i<nums.length-1;i++){	   if(nums[i]<nums[i+1])count++;	}	if(count==0)c=false;	nums=nextPermutation(nums);//即為上個代碼的函數      }      return out;}

　　這個方法對Permutations II也是一樣的思路，畢竟多了重復元素，只是換湯不換藥。

將到Permutation Sequence這個問題，一開始我也打算采用這個方法（因為上癮了，更因為偷懶，不思考，想節約時間），看似很簡單，結果竟然超時了：

public String getPermutation(int n, int k) {        String out=new String();        if(n==0)return out;        int[]a=new int[n];        for(int i=1;i<=n;i++)a[i-1]=i;        int count=1;        while(count!=k){            a=nextPermutation(a);            count++;        }        for(int i=0;i<a.length;i++)out+=a[i];        return out;    }

后來思考了下，發現有簡單的方法，這題的好處在于不用列出所有的排列，而且不需要知道此排列之前的所有排列，leetcode給的tag是Backtracking，一開始真給我繞進去了，后來發現其實完全可以猜出來這第k個排列是啥，不需要回溯（原因在于集合中這n個元素是從小到大，即從1...n的這么幾個數）。可以這么想，n個元素的全排列個數是n！，n-1個的話是（n-1）！。所以求第k個排列，我們完全可以知道這個排列是以那個數作為前綴的，這個數即為1...n，這n個數里的第k/（n-1）！。同理，可以知道第二個前綴的數是那個（此時k=k%（n-1）！）......直到k%x!=0

 public String getPermutation(int n, int k) {    String out=new String();        if(n==0)return out;        int p=1;        List<Integer>l=new ArrayList<Integer>();        for(int i=1;i<n;i++){
           p=p*i;
           l.add(i);
        }        l.add(n);        int s=k/p;        int y=k%p;        int t=n-1;        while(y!=0){            out+=l.get(s);            l.remove(l.indexOf(l.get(s)));            k=y;            p=p/t;            t--;            s=k/p;            y=k%p;        }        out+=l.get(s-1); //為什么s-1？因為余數已經是0了，相當于我們應該取前綴是l.get(s-1)這個數的最大的排列        l.remove(l.indexOf(l.get(s-1)));        for(int i=l.size()-1;i>=0;i--)out+=l.get(i);//在確定前綴的前提下的最大排列，即能用list里剩余的數構成的最大的數        return out;    }