组合数学与算法题-排列组合篇
2019-01-19 本文已影响0人
rosewind
前言
之前刷过一些leetcode的题目，这学期修了组合数学这门课，让我感受颇多。课程上更关注的是数学上的解法，并没有讲到具体的用某种语言实现，并没有深入地讲为什么这样做就是对的。结合我的经验，想分享一下我的理解。
leetcode 31.下一个全排列
2个关键点:
-
下一个全排列比当前的大(字典序)
-
增量要是最小的
一些例子:
-
1243 -> 1324,要使1243更大，从右往左看，43已经是最大的了,所以下一个肯定是13开头，故交换2,3得到1342,后2位42肯定无法保证增量最小，故翻转42，得到1324,即为所求
-
4321 -> 1234,从右往左看，全部递增，故这是最后一个序列了，翻转整个序列，得到1234,符合题目的要求
class Solution {
public void nextPermutation(int[] nums) {
if(nums == null || nums.length == 1) return;
//从右向左，找到破坏递增规律的第一个数
int n = nums.length;
int index = -1;
for(int i = n-2; i >= 0; i--){
if(nums[i] < nums[i+1]){
index = i;
break;
}
}
//找到比nums[index]大的第一个数
//交换nums[index]与这个nums[i]
if(index != -1){
for(int i = n-1; i>= 0; i--){
if(nums[i] > nums[index]){
int tmp = nums[i];
nums[i] = nums[index];
nums[index] = tmp;
break;
}
}
}
//翻转数组，范围为[index+1,n-1]，这样便使增量最小
//如果是最后一个排列，如[3,2,1],index为-1，翻转整个序列
reverseArray(nums, index+1, n-1);
}
public void reverseArray(int[] nums,int start,int end){
for(int i = start, j = end;i <= j; i++,j--){
//交换nums[i]与nums[j]
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
leetcode 60.第k个全排列
n=3时，共有3!个排列
-
123
-
132
-
213
-
231
-
312
-
321
关键:
-
每2个看成一组，每一组内第一位都是相同的,如123,132
-
即每n-1个看成一组，总共有n组(n!=n*(n-1))
-
若第0位已确定，剩下就是n-1个数的排列，可分成n-1组，每个组内(n-2)!个
以n=3,k=4为例:
-
为了跟程序里的小标对应,从0开始，k=k-1=3
-
3/2!=1余1,说明第0位是[1,2,3]中下标为1的数,即2
-
余数为1，剩下2个数,1/1!=1余0,[1,3]中下标为1的数即3
-
只剩下1,故结果是231
这其实可以归纳出一个数学公式，康托展开与逆展开
class Solution {
public String getPermutation(int n, int k) {
//需要用到一点数学知识，康托展开
StringBuilder sb = new StringBuilder();
List<Integer> info = new ArrayList<Integer>();
for(int i=1;i<=n;i++){
info.add(i);
}
int factor=1;
k=k-1;
//计算出(k-1)!
for(int i = 2;i<=n-1;i++){
factor *= i;
}
for(int i=n-1;i>=1;i--){
int p = k/factor;//商
k = k%factor;//余数
sb.append(info.get(p));
//移除
info.remove(p);
//更新
factor /= i;
}
sb.append(info.get(0));//最后info中只剩下一个
return sb.toString();
}
}
已知全排列求k
给出231,求k
如果真的理解了上面的分组，很容易就可以列出式子:
因为我们小标从0开始，最后再加1即可
理解一下这个式子的含义:就是求比231小的排列有多少个
只有这几种可能{1, ,}(以1开头的排列,共有2个)
{2,1,}(以2,1,开头的排列,只有1个)
所以231是排在第4的
