学步园

这种题目一般有两种方法，比较直接的方法就是使用循坏，但是对于这种方法只有r小于等于4时才是可行的，这个时候复杂度是（O（n^r））,可知，这种方法的时间复杂度很高，而且这种循环机制严重依赖r，通过r来控制循环层数，因此这种方法不具有普遍性。最常用的方法就是使用递归。

在循环算法设计中，每个组合中的数据都是从大到小排列是必须的，因为递归算法设计时要找出大规模问题与小规模问题之间的关系。

当 n = 5, r = 3时，从大到小排列的组合数目是：

     5   4  3

     5   4  2

     5   4  1

     5   3  2

     5   3  1

     5   2  1

     4   3  2

     4   3  1

     3   2  1

总得组合数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,
通过对这个题目的深入了解和探究，对递归有了较深的认识。