最近在做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
(#换成@)。