精华内容
下载资源
问答
  • 从n个数中取m个全排列

    千次阅读 2018-05-24 18:03:52
    #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...
    #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}通过以上例子,我们...

    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});...全排列组合,如果集合有4元素,则全

    (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都是全新的变量和集合
    			}
    		}
    		
    	}
    
    }


    展开全文
  • n个元素全排列

    2018-05-30 16:03:39
    适用于算法课程求n个元素的全排列从n个不同元素取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 公式:全排列数f(n)=n!(定义0!=1)
  • * 一、在n个球中任意取出m个,有多少中取法 * 例如: abcd 4个球中取出 2 个球 * 所有情况举例:ab ac ad bc bd cd * 思路:上述中我们可以发现,取出的球可以分为两个阵列,一个是含有a(也可以是其他...
    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);
    	}
    }
    
    
    
    展开全文
  • 从n个不同元素取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。网上到处都是全排列的递归算法代码,但当m SELECTED_COUNT == 1,如果...
  • 全排列

    2019-08-21 09:58:53
    从n个不同元素取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 公式:全排列数f(n)=n!(定义0!=1) 算法:递归算法=》网络上偷了一...
  • * 全排列从n个不同元素取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。  * [1,n],[1,n-1],[1,n-2]……[1]  *  */  public ...
  • =n)个数按照一定的顺序进行排成一个列,叫作从n个元素中取m个元素的一个排列。不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数,称为排列数。 全排列 从n个元素取出n个元素的一个排列,称为一...
  • 全排列算法

    2018-03-21 20:02:53
    =n)个数按照一定的顺序进行排成一个列,叫作从n个元素中取m个元素的一个排列。由排列的定义,显然不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数,称为排列数。从n个元素取出n个元素的一个排列...
  • 全排列问题

    2019-04-03 20:12:44
    全排列问题 ...=n)个元素,按照一定的顺序排列起来,叫做从n个不同元素取出m个元素的一个排列,当m=n时所有的排列情况叫全排列。现输入n个递增的数,请你输出这n个数的全排列全排列输出顺序如样例...
  • 全排列实现

    2019-03-14 10:09:26
    全排列从n个不同元素取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 公式:全排列数f(n)=n!(定义0!=1) 举个例子 abc全排列: ...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 274
精华内容 109
热门标签
关键字:

从n中取m个全排列