精华内容
下载资源
问答
  • 从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; 
    }

    展开全文
  • 题目描述 输入n,在1-n中取m个数字进行全排列输入样例 3 2输出样例 3 2 1 2 1 3 2 1 2 3 3 1 3 2

     从1-n中取m个数字进行全排列

    题目描述
    输入n,在1-n中取m个数字进行全排列
    输入样例
    3
    2
    输出样例
    3
    2
    1 2
    1 3
    2 1
    2 3
    3 1
    3 2

     思路:跟全排列代码几乎完全相同,只是更改了最终条件
    step==n+1 改成step==m+1时停止
    j<=n 改成j<=m
    很多DFS问题都是在条件上更改,增加条件限制
    框架一的话就是for内else的if条件更改

    //全排列问题衍生:1-n个数取n个数字全排列
    #include<iostream>
    using namespace std;
    int a[10], vis[10];//vis数组记录是否用过,用过为1,没用为0,a数组记录每次的具体情况
    int n,m;
    int dfs(int step)//为什么是int类型的函数
    {
    	if (step == m+ 1) //如果到达目的地,输出排列
    	{
    		for (int j = 1; j <=m; j++) { cout << a[j] << " "; }
    		cout << endl;
    	}
    	else
    	{
    		for (int i = 1; i <= n; i++)
    		{
    			if (vis[i] == 0)//向前一步走的通:没被用过
    			{
    				a[step] = i;//保存当前结果
    				vis[i] = 1;//这个格子标记为用过
    				dfs(step + 1);
    				vis[i] = 0;//回溯
    			}
    		}
    	}
    	return 0;
    }
    int main()
    {
    	cin >> n>>m;
    	dfs(1);
    }
    

    从1-n取m个数全排列,从小到大数无重复输出

    题目描述

    从1-n取m个数全排列,从小到大数无重复输出

    输入样例
    5 3
    输出样例
    1 2 3
    1 2 4
    1 2 5
    1 3 4
    1 3 5
    1 4 5
    2 3 4
    2 3 5
    2 4 5
    3 4 5

    思路:跟全排列代码几乎完全相同,只是更改了最终条件
    step==n+1 改成step==m+1时停止
    j<=n 改成j<=m
    for内if条件增加限制,必须a数组中后一个元素大于前一个元素

    //全排列问题衍生:1-n个数取n个数字全排列
    #include<iostream>
    using namespace std;
    int a[10], vis[10];//vis数组记录是否用过,用过为1,没用为0,a数组记录每次的具体情况
    int n, m;
    int dfs(int step)//为什么是int类型的函数
    {
    	if (step == m + 1) //如果到达目的地,输出排列
    	{
    		for (int j = 1; j <= m; j++) { cout <<"  "<< a[j]; }
    		cout << endl;
    	}
    	else
    	{
    		for (int i = 1; i <= n; i++)
    		{
    			if (vis[i] == 0&&a[step-1]<i)//向前一步走的通:没被用过
    			{
    				a[step] = i;//保存当前结果
    				vis[i] = 1;//这个格子标记为用过
    				dfs(step + 1);
    				vis[i] = 0;//回溯
    			}
    		}
    	}
    	return 0;
    }
    int main()
    {
    	cin >> n >> m;
    	dfs(1);
    }
    

     

    展开全文
  • 这是递归算法(perm函数)用来生成n中取m的排列(数字可以重复但排序不重复)。请用堆栈消除递归 #include void perm(int flag[],int a[], int k, int n, int m) { int i; if(k==m) { for(i=0;i<m;i++) ...
  • (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都是全新的变量和集合
    			}
    		}
    		
    	}
    
    }


    展开全文
  • #include <iostream> #include <string> #include <vector>...//m个数的全排列 void AllRange(vector<int>& nums, vector<vector<int>>& sub, int k, int m) {
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <stack>
    using namespace std;
    
    //m个数的全排列
    void AllRange(vector<int>& nums, vector<vector<int>>& sub, int k, int m) {
    	if (k == m) {
    		sub.push_back(nums);
    	}
    	else {
    		int i = k;
    		for (; i < m; i++) {
    			swap(nums[i], nums[k]);
    			AllRange(nums, sub, k + 1, m);
    			swap(nums[k], nums[i]);
    		}
    	}
    }
    // 取n个数出来
    vector<int> s;
    void dfs(vector<int>& a, int n, int m, int index, int nowk)
    {
    	if (nowk == m) {//当我挑选的数已经够得时候,就把它输出。
    		for (int i = 0; i < m; i++) {
    			cout << s[i] << ' ';
    		}
    		cout << endl;
    		return;
    	}
    	if (index < n) {
    		s.push_back(a[index]);
    		dfs(a, n, m, index + 1, nowk + 1);
    		s.pop_back();
    		dfs(a, n, m, index + 1, nowk);
    	} 
    }
    
    int main() {
    	vector<int> nums;
    	int n;
    	int a;
    	string s;
    	cin >> s;
    	n = s.back() - '0';//n
    	for (int i = 0; i < s.size() - 2;i++) {
    		if (i % 2) {
    			nums.push_back(s[i] - '0');
    		}
    	}
    	dfs(nums, nums.size(), n, 0, 0);
    	return 0;
    }
    
    展开全文
  • 下面的代码主要解决的问题是:从m个各不相同的元素取出n个,进行全排列,得到所有可能的结果。 即:输入为字符数组(数组内每字符均不相同)和n,返回由这些字符组成的所有长度为n的字符串。
  • 用DFS从n个选出m个数 假设1-12选出5不同的数,问有多少种情况。 不考虑每数的顺序 两种写法,开始点不同 1)第一种DFS的开始点是以1-12的一为起点,然后依次考虑后面的数。 2)第二种是0开始,0...
  • N个取m个数的全排列非递归

    千次阅读 2014-05-31 15:25:22
    但一般化就是从N个取m个出来,每次不放回,输出它们的排列方式。 N个色子的组合输出 http://blog.csdn.net/lin200753/article/details/27797391 从而 也可以采用回溯法来解决上面的问题,不允许重复数字或...
  • n个元素全排列

    2018-05-30 16:03:39
    适用于算法课程求n个元素的全排列从n个不同元素取m(m≤n元素,按照一定的顺序排列起来,叫做从n个不同元素取出m元素的一排列。当m=n时所有的排列情况叫全排列。 公式:全排列数f(n)=n!(定义0!=1)
  • 从n个选取m个数的组合及全排列 题目描述: 给定两整数nm,输出(1,2,…,n)选出m个数的所有组合。 输入: 每测试文件含有多数据,输入两整数n,m(0<m<=n<=10)。输入到文件末尾结束。 输出: ...
  • C++:n个全排列n个中取k

    千次阅读 2019-11-01 11:05:43
    题目:...解题思路: //n个中取k数 递归写法: //参考:https://blog.csdn.net/hf19931101/article/details/79452799 class Solution { public: vector<string> results; int minMa...
  • 利用递归,来求任意n个取出m个数的全排列 分析: 求n个数的全排列,也就是: 第一数不动,将后面的n-1数全排 将第二数和第一数交换,将后面n-1全排列(注意要换回来) 将第三数和第一数...
  • * 一、在n个任意取出m个,有多少中取法 * 例如: abcd 4取出 2 球 * 所有情况举例:ab ac ad bc bd cd * 思路:上述我们可以发现,取出的球可以分为两阵列,一是含有a(也可以是其他...
  • 下列乘法竖式,每一星号代表一数位。若出现的数字有且仅有2,3,5,7四种,你能将此竖式完全还原嘛? 答案:775*33 = 25575(2325+23250) 进一步,若将题目的2,3,5,7改为其他互异的四数字,还...
  • n个数选取m个进行全排列

    千次阅读 2017-03-05 15:55:11
    # include using namespace std; int sum[100]; void function(int m,int k) { int i,j; for(i=m;i>=k;i–) { a[k]=i; if(k>1) function(i-1,k-1);
  • 大佬的代码很强,我递归不大好,转载来学习下,1到n全排列原文地址:...1到n中选m个数的排列原文地址 https://blog.csdn.net/shaoxiaohu1/article/details/50684782 1到n全排列 #include<iostream&...
  • 一、在n个,任意取出m个球(不放回),有多少种不同的方法 运行截图: 代码如下: package sf_1; public class Main { public static int f(int n,int m){ /* * a b c ......ab ac bc * 内部含有一...
  • 从n个不同元素取m(m≤n元素,按照一定的顺序排列起来,叫做从n个不同元素取出m元素的一排列。当m=n时所有的排列情况叫全排列。网上到处都是全排列的递归算法代码,但当m SELECTED_COUNT == 1,如果...
  • m个A与n个B的全排列个数 package com.aiqiongdiao; public class Main { public static int g(int m,int n){ if(m==0||n==0){ //出口:不断降,总会为0 return 1; //为一种情况,mn之间没有大小约束 }...
  • 给定一由不同的小写字母组成的字符串,输出这字符串的所有全排列。 我们假设对于小写字母有’a’ < ‘b’ < … < ‘y’ < ‘z’,而且给定的字符串的字母已经按照从小到大的顺序排列。 输入 输入...
  • package lianxi; import java.util.ArrayList; import java.util.List; public class e { ... public static void doit(char[] chars, int n) { //判断非法输入 if (n <= 0 || chars == null) { ...
  • //从N个中取M个进行排列 M=N全排列 public static void test(List ready, List notReady) { if (ready.size() == NUM) { System.out.println(ready); COUNT++; return; } else { for (int i =...
  • n个元素的全排列(递归+去重)

    万次阅读 2016-06-16 13:10:37
    排列组合是算法常用的基本工具,如何在c语言实现排列组合呢?思路如下:本文主要探讨递归实现,由于递归将问题逐级分解,因此相对比较容易理解,...表示n个元素全排列的个数(假设集合没有重复元素)。例如:{1, 2,
  • * 全排列从n个不同元素取m(m≤n)元素,按照一定的顺序排列起来,叫做从n个不同元素取出m元素的一排列。当m=n时所有的排列情况叫全排列。  * [1,n],[1,n-1],[1,n-2]……[1]  *  */  public ...
  • python实现N个元素的全排列问题

    千次阅读 2020-06-03 14:48:02
    利用python来实现N个元素的全排列。 利用一list来存储元素 这里考虑的是无重复元素的全排列 代码实现 实际上,可以将查找一个全排列的过程看成是一棵NN表示list的长度)叉树的深度优先遍历。当到达最大深度...
  • 全排列

    2019-02-17 20:29:27
    n 不同元素 m(mn) 元素,按照一定的顺序排列起来,叫做 n 不同元素取出 m 元素的一排列。当 m=n 时所有的排列情况叫全排列。今天这道题目很简单就是给你一整数 n ,计算 [1,n] 所有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,801
精华内容 2,720
关键字:

从n中取m个全排列