算法|排列组合 从n个自然数中取出r个数的组合
这种题目一般有两种方法,比较直接的方法就是使用循坏,但是对于这种方法只有r小于等于4时才是可行的,这个时候复杂度是(O(n^r)),可知,这种方法的时间复杂度很高,而且这种循环机制严重依赖r,通过r来控制循环层数,因此这种方法不具有普遍性。最常用的方法就是使用递归。
在循环算法设计中,每个组合中的数据都是从大到小排列是必须的,因为递归算法设计时要找出大规模问题与小规模问题之间的关系。
当 n = 5, r = 3时,从大到小排列的组合数目是:
543
542
541
532
531
521
【算法|排列组合 从n个自然数中取出r个数的组合】432
431
321
总得组合数total = 10;
分析以上数据可以知道,首先固定第一个数5,其后求解n=4,r=2的组合数,共6个组合,其次固定第一个数4,其后就是求解n=3,r=2的组合数,总共是3个组合数;最后固定第一个数3,其后就是求解n=2,r=2的组合数,共一个组合。
递归思路就是:n个数中r个数组合递推到n-1个树种r-1个数有组合,n-2个数中r-1个数有组合,。。。r-1个数中r-1个数组合;当r=1时,递归终止;
package com.base;
public class Permutation {
static int a[] = new int[100];
public static void f(int n,int r){
if(r == 1){
a[r-1] = n;
int j = 0;
while(a[j]!= 0){
j++;
}
for(int i = j-1;
i >= 0;
i --){
System.out.print(a[i]+",");
}
System.out.println();
}
else{
a[r-1] = n;
for(int j = n-1;
j >= r-1;
j --){
f(j,r-1);
}
}
}
public static void main(String[] args) {
int n = 6,r = 3;
for(int i = n;
i >= r;
i --){
f(i,r);
}
}
}
结果如下所示: 6,5,4,
6,5,3,
6,5,2,
6,5,1,
6,4,3,
6,4,2,
6,4,1,
6,3,2,
6,3,1,
6,2,1,
5,4,3,
5,4,2,
5,4,1,
5,3,2,
5,3,1,
5,2,1,
4,3,2,
4,3,1,
4,2,1,
3,2,1,
通过对这个题目的深入了解和探究,对递归有了较深的认识。
推荐阅读
- Docker应用:容器间通信与Mariadb数据库主从复制
- 一个人的碎碎念
- 我从来不做坏事
- 画解算法(1.|画解算法:1. 两数之和)
- 从蓦然回首到花开在眼前,都是为了更好的明天。
- Guava|Guava RateLimiter与限流算法
- 西湖游
- 改变自己,先从自我反思开始
- leetcode|leetcode 92. 反转链表 II
- 从我的第一张健身卡谈传统健身房