#include<iostream> 
using namespace std; 
int a[100]; //存储排列的数
void fun(int m,int k) 
{ 
    int i,j; 
    for(i=m;i>=k;i--) 
    { 
        a[k]=i; 
        if(k>1) 
            fun(i-1,k-1); 
        else 
        { 
            for(j=a[0];j>0;j--) 
                cout<<a[j]<<"\t"; 
            cout<<endl; 
        } 
    } 
} 


int main() 
{ 
    int n,r; 
    cout<<"请输入n和r的值:"<<endl; 
    cin>>n>>r; 
    if(r>n) 
        cout<<"输入n和r的值错误!"<<endl; 
    else 
    { 
        a[0]=r; 
        function(n,r); 
    } 
    return 0; 
}

NOI国家集训队论文集
(1)全排列组合的递归规律：
集合s的全排列组合 all(s)=n+all(s-n);其中n为已经取出的集合
以集合 s={1,2,3}为例,则s的全排列组合为all(s)={1}+all({2,3});其中n={1},s-n={2,3}
通过以上例子，我们可以知道上述算法可以用递归来解决。
我们取极端情况，如果集合s为空，那么说明不需要再进行递归。
全排列组合，如果集合有4个元素，，则全排列组合的个数为 A(4,4)=4*3*2*1=24种，代码如下：
package dataStructer;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class FullPermutation {//全排列组合
private int n;
public FullPermutation ()
{
this.n=0;
}
public  void listAll(List candidate,String prefix)
{
if(candidate.isEmpty())
{
System.out.println(prefix);
this.n++;
}
for(int i=0;i
{
List temp=new LinkedList(candidate);//转换成linkList,移除一个对象是在不影响原来队列的基础上的
String s1=prefix+temp.remove(i);//用于保存排列组合生成的结果
listAll(temp,s1);//注意，这里temp和s1都是全新的集合和字符串，并不是一直对一个集合来进行操作
}
}
public int getN() {
return n;
}
public void setN(int n) {
this.n = n;
}
public static void main(String[] args) {
String []arr={"1","2","3","4"};
FullPermutation f=new FullPermutation();
f.listAll(Arrays.asList(arr),"");
System.out.println("所有的排列个数："+f.getN());
}
}
(2)m个数据集合中选出n个数据(有序)
m个数据集合中选出n个数据规律为：get({m},n)=t+get(集合{m-t},m-t的大小)
考虑极端的情况，如果集合m里只取一个元素，那么直接把这个元素取出来即可。
如何集合有4个元素，取出其中的两个有序元素个数为A(4,2)=4*3=12
package dataStructer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class mAn {
private int all;
public mAn()
{
this.all=0;
}
public int getAll() {
return all;
}
public void setAll(int all) {
this.all = all;
}
public static void main(String[] args) {
String[] n ={"1","2","3","4"};
mAn m=new mAn();
List lst = Arrays.asList(n);
m.take("",2,lst);
System.out.println(m.getAll());
}
public  void take(String s, int total, List lst) {
for (int i = 0; i < lst.size(); i++) {
//System.out.println("i="+i);
List templst=new LinkedList(lst);
String n =  (String) templst.remove(i);// 取出来的数字
String str = s + n;
if (total == 1) {
System.out.println(str);//以最极端 n个里面只取一个，直接把取出来的结果输出即可
//total=all;
all++;
} else {
int temp=total-1;//在同一层中total总量不能减,不能再原有变量的基础上
take(str, temp, templst);// 这里的temp以及templst都是全新的变量和集合
}
}
}
}
版权声明：本文为博主原创文章，未经博主允许不得转载。

（1）全排列组合的递归规律：
集合s的全排列组合 all(s)=n+all(s-n);其中n为已经取出的集合
以集合 s={1,2,3}为例,则s的全排列组合为all(s)={1}+all({2,3});其中n={1},s-n={2,3}
通过以上例子，我们可以知道上述算法可以用递归来解决。
我们取极端情况，如果集合s为空，那么说明不需要再进行递归。
全排列组合，如果集合有4个元素，则全排列组合的个数为 A(4,4)=4*3*2*1=24种，代码如下：
package dataStructer;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class FullPermutation {//全排列组合
	private int n;
	public FullPermutation ()
	{
		this.n=0;
	}
	public  void listAll(List candidate,String prefix)
	{
		
		if(candidate.isEmpty())
		{
			System.out.println(prefix);
			this.n++;
		}
		for(int i=0;i<candidate.size();i++)
		{
			List temp=new LinkedList(candidate);//转换成linkList,移除一个对象是在不影响原来队列的基础上的
		    String s1=prefix+temp.remove(i);//用于保存排列组合生成的结果
			listAll(temp,s1);//注意，这里temp和s1都是全新的集合和字符串，并不是一直对一个集合来进行操作
			
		}
		
	}
	public int getN() {
		return n;
	}
	public void setN(int n) {
		this.n = n;
	}
	public static void main(String[] args) {
		String []arr={"1","2","3","4"};
		FullPermutation f=new FullPermutation();
		f.listAll(Arrays.asList(arr),"");
		System.out.println("所有的排列个数："+f.getN());
	}

}

（2）m个数据集合中选出n个数据（有序）
m个数据集合中选出n个数据规律为：get({m},n)=t+get(集合{m-t},m-t的大小)
考虑极端的情况，如果集合m里只取一个元素，那么直接把这个元素取出来即可。
如何集合有4个元素，取出其中的两个有序元素个数为A(4,2)=4*3=12
 
package dataStructer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class mAn {
	private int all;
	public mAn()
	{
		this.all=0;
	}
	public int getAll() {
		return all;
	}
	public void setAll(int all) {
		this.all = all;
	}
	public static void main(String[] args) {
		String[] n ={"1","2","3","4"};
		mAn m=new mAn();
		List lst = Arrays.asList(n);
        m.take("",2,lst);
        System.out.println(m.getAll());
	}

	public  void take(String s, int total, List lst) {
		for (int i = 0; i < lst.size(); i++) {
			//System.out.println("i="+i);
			List templst=new LinkedList(lst);
			String n =  (String) templst.remove(i);// 取出来的数字
			String str = s + n;
			if (total == 1) {
				System.out.println(str);//以最极端 n个里面只取一个，直接把取出来的结果输出即可
				//total=all;
				all++;
			
			} else {
				int temp=total-1;//在同一层中total总量不能减,不能再原有变量的基础上
				take(str, temp, templst);// 这里的temp以及templst都是全新的变量和集合
			}
		}
		
	}

}

package digui;
/**
 * @author : HuXuehao
 * @date : 2021年3月2日下午5:26:14
 * @version : 
*/
public class classical_case {
	/*
	 * 一、在n个球中任意取出m个，有多少中取法
	 * 例如：从 abcd 4个球中取出 2 个球
	 *     所有情况举例：ab ac ad bc bd cd
	 *     思路：从上述中我们可以发现，取出的球可以分为两个阵列，一个是含有a（也可以是其他）的，
	 *     		一个是不含有a的
	 *     总结：① ab ac ad 可以理解成默认取出的球中含有a，也就是从n-1（因为a默认已经取出）个
	 *     		球中取出m-1（因为默认已经取出a了）个球；② bc bd cd 是不含有a的球，可以理解成
	 *     		取出的球中不能含有a，也就是从n-1（把a排除在外，才能保证取出的球不含有a）中取出
	 *     		m个球
	 */
	public static int getTargetNum(int n, int m) {
		if(n < m) return 0; //当n < m时，无法取球
		if(n == m ) return 1; //当n == m时，只有一种可能性
		if(m == 0) return 1; //当取出0个球时，认为只有一种可能
		
		return getTargetNum(n-1, m-1)/*①*/ + getTargetNum(n-1, m)/*②*/;
	}
	
	/* 二、求 n个元素的全排列
	 * 方案1：（思路没有问题，没有通过代码实现，我猜测它的时间复杂度会很大）
	 * 思路：求n个元素的全排列时，先求出n-1个元素的全排列x，将第一个元素插入每个全排列x的不同位置
	 *      求n-1个元素的全排列x时，先求n-2个元素的全排列y，将第n-1个元素插入每个全排列y的不同位置
	 *      ......
	 * 例如： dabc
	 * 		求 abc 的全排列
	 * 		求bc 的全排列
	 * 	        （c的全排列）求c的全排列：
	 * 			c
	 * 	        （bc的全排列）将b 依次插入到 c 的全排列的空隙中得到bc的全排列：
	 * 			bc cb
	 * 	        （abc）将a 依次插入到每一个bc的全排列的空隙中得到abc的全排列:
	 * 			abc acb bac bca cab aba
	 * 	        （dabc）将 d 依次插入到 bc 的全排列的空隙中得到dabc的全排列:
	 * 			dabc adbc abdc abcd
	 * 			dacb adcb acdb acbd
	 * 			dbac bdac badc bacd
	 * 			dbca bdca bcda bcad
	 * 			dcab cdab cadb cabd
	 * 			daba adba abda abad
	 * 
	 * 方案2：（重点理解）***
	 * 例如：abc 
	 * abc acb bac bca cab cba
	 * 我们不难发现，将数组中的每一个元素与第一个元素进行交换，然后进行全排列 	   
	 */
	public static void allSort(char []data,int key) {
		if(key == data.length) {
			for(int i = 0;i < data.length; i++) {
				System.out.print(data[i] + "");
			}
			System.out.println();
		}
		for(int i = key; i < data.length; i++) {
//			试探
			{char t = data[key];data[key] = data[i];data[i] = t;}
			allSort(data, key+1);
//			回溯
			{char t = data[key];data[key] = data[i];data[i] = t;}
		}
	}
	
	/*
	 * 三、求两个串的最大公共子序列的长度（只是限于可解上面，软法的优化是很大的问题）
	 * 
	 */
	public static int maxPubSubList(String str1,String str2) {
		//出口
		if(str1.length() == 0 || str2.length() == 0) return 0;
		
		//如果第一个字符相等，那么就以下一个字符为开头的子串求最大公共子序列长度x,x+1就是两个串的最大公共子序列的长度
		if(str1.charAt(0) == str2.charAt(0)) {
			return maxPubSubList(str1.substring(1), str2.substring(1)) + 1;
		}else {
			//如果第一个不同，那么就尝试分别将其中一个的开头字符去掉，再分别求两个串最大公共子序列长度，最大公共子序列取长度长的
			return Math.max(maxPubSubList(str1, str2.substring(1)), maxPubSubList(str1.substring(1), str2));
		}
	}

	public static void main(String[] args) {
		/*System.out.println("------------------");
		int n = 5;
		int m =3;
		System.out.println(getTargetNum(n, m));
		
		System.out.println("------------------");
		char []c = "abcd".toCharArray();
		allSort(c, 0);*/
		
//		System.out.println("------------------");
//		System.out.println(maxPubSubList("abc", "eafbg"));
		System.out.println(0);
	}
}