你的位置:首页 > Java教程

[Java教程]关于排列问题的一系列归类


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

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