最近在做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]
     
      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
     

      介绍了Next Permutatio的方法，下面我们可以很容易将这个方法用在Permutations这个题目上，首先我们队集合里的元素进行sort产生第一个排列，然后调用Next Permutatio，不断产生新的排列，leetcode上这种方法亲测可行。

public List
     
      
       > permute(int[] nums) {     List
       
        
         > out=new ArrayList
         
          
           >(); if(nums.length==0)return out; Arrays.sort(nums); boolean c=true; while(c){ List
           
            inter=new ArrayList
            
             (); for(int i=0;i
            
           
          
         
        
       
      
     

　　 这个方法对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

      后来思考了下，发现有简单的方法，这题的好处在于不用列出所有的排列，而且不需要知道此排列之前的所有排列，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
     
      l=new ArrayList
      
       ();        for(int i=1;i
       
        =0;i--)out+=l.get(i);//在确定前缀的前提下的最大排列，即能用list里剩余的数构成的最大的数        return out;    }
       
      
     

     方法应该还有很多，这里只是看到了这几个题，所以稍微归纳了一下，不到之处，请指出，或者有更好的方法，请指教！