组合数学与算法问题 - 排列与组合
前言
之前刷过一些leetcode的题目,这学期修了组合数学这门课,让我感受颇多。课程上更关注的是数学上的解法,并没有讲到具体的用某种语言实现,并没有深入地讲为什么这样做就是对的。结合我的经验,想分享一下我的理解。
leetcode 31.下一个全排列
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个全排列
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的
上一篇: 通过位操作的组合算法
下一篇: 排列组合总结
推荐阅读
-
简易版TGU算法课程:递归与分治方法下的Test1问题E - 组合数学详解题解
-
蓝桥杯编程大赛:玩转C++中的排列与组合技巧
-
轻松掌握 - 组合数学入门:组合数的基础与取模应用,以及中国剩余定理(CRT)详解
-
组合数学--排列和组合--一个混淆点、关于连续抽签数字问题的解决方案、循环数列与 n 次无向完整图的哈密顿循环之间的关系
-
组合数学_第 1 章_排列与组合
-
[组合数学]集合的排列与组合问题举例 ( 排列 | 组合 | 循环排列 | 二项式定理 )
-
[算法] 用 0 到 9 生成十位数的所有排列组合,将字母组合成无字天书 两个算法问题 - Java 代码参考
-
数学中的排列组合问题
-
组合数学与算法问题 - 排列与组合
-
[算法] 组合数学 - 排列数生成算法 (I) - 备注