你的位置:首页 > 软件开发 > Java > 关于排列问题的一系列归类

关于排列问题的一系列归类

发布时间:2015-11-09 17:00:10
最近在做leetcode的时候,做到了一些排列的问题,比如Next Permutation(求已知当前排列的下一个全排列),Permutations(给定一个整型集合,求全排列),Permutations II(与Permutations类似,只是增加了重复元素出现的情况),Pe ...

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

原标题:关于排列问题的一系列归类

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

可能感兴趣文章

我的浏览记录