[算法] 求排列组合: 从n个数中任选m个数组成一个新数

拼搏现实的明天。 2022-06-06 11:54 212阅读 0赞

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    // 求排列组合算法: C(n, m): 从n个数中任选m个数组成一个新的数, 求有多少种组合, 分别是什么 
    // 从v[]里任选m个元素组成一个组合, 与顺序无关
    template<class T>
    vector<vector<T>> fun(vector<T> v, int m)
    {
    	if(v.size() < m)
    		return {};				// 找不到这样的组合
    
    	vector<vector<T>> ret;
    	if(v.size() == m)			// v[]中任选m个数
    	{
    	   	ret.push_back(v);		// 唯一的一个组合
    
    		return ret;
    	}
    	else if(m == 1)				// v[]中任选1个数
    	{
    		for(auto& it : v)
    		{
    			ret.push_back(vector<T> {it});
    		}
    
    		return ret;
    	}
    
    	while(v.size() >= m)
    	{
    		auto first = v.front();
    		v.erase(v.begin());
    
    		// 在剩下的v[1~]中任选m-1个数
    		auto res = fun(v, m - 1);
    		for(auto& it : res)
    		{
    			it.insert(it.begin(), first);
    			ret.push_back(it);
    		}
    	}
    
    	return ret;
    }
    
    int main()
    {
        vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    	int m = 3;
    
    	auto res = fun(v, m);
    	for(auto& it : res)
    	{
    		for(auto& it2 : it)
    			printf("%d ", it2);
    		printf("\n");
    	}
    	printf("res.size=%d\n", res.size());
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关 n个数求前m个数的大小

一、描述 n个数求前m个数的大小二、分析堆排序就是先求出最大的数，然后求出次大的数，然后求出第三大的数，依次类推，而这个题只要求求出前m个大的数，所以用堆排序应该是效

布满荆棘的人生/ 2023年12月31日 07:20/ 0 赞/ 48 阅读

相关【C】 4个数排列组合

使用VS2019 ISO C++14 标准 (/std:c++14) 4个数排列组合 //有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？

旧城等待，/ 2023年03月14日 10:50/ 0 赞/ 232 阅读

相关打印n个数中任意m个数组合

消除k的二进制数的最后一个1： k = k & (k-1); 计算x的二进制数的最后一个1： lowbit(x) = x & -x; include <i

绝地灬酷狼/ 2023年02月25日 03:39/ 0 赞/ 51 阅读

相关从n个数中选取m个数的所有组合

题目： ![在这里插入图片描述][2020060421241697.png] n个数1,2,...,n，从这n个数中任意选m个数，输出所有不同组合，共有C(n,

蔚落/ 2023年02月15日 10:03/ 0 赞/ 63 阅读

相关求一个数中1的个数

给定多个十进制的数，求二进制情况下1的个数 include <iostream> using namespace std; int

Bertha 。/ 2023年01月24日 04:21/ 0 赞/ 87 阅读

相关算法-求二进制数中1的个数

问题描述任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4 这也是一道比较经典的题目

女爷i/ 2022年07月28日 05:07/ 0 赞/ 210 阅读

相关从1到m随机n个数

以下代码实现从1到m，随机n个数 public static int[] random(int m, int n) { Random r =

快来打我*/ 2022年06月15日 07:48/ 0 赞/ 234 阅读

相关 [算法] 求排列组合: 从n个数中任选m个数组成一个新数

include <iostream> include <vector> using namespace std; // 求排

拼搏现实的明天。/ 2022年06月06日 11:54/ 0 赞/ 213 阅读

相关 m个数字任选n个数组进行组合

using System; using System.Collections; namespace ConsoleApplication

青旅半醒/ 2022年06月02日 02:29/ 0 赞/ 214 阅读

相关从N个数中等概率打印M个数

![20180412102048406][] //从N个数中等概率打印M个数 public class PrintNum{ /

太过爱你忘了你带给我的痛/ 2022年05月27日 05:15/ 0 赞/ 221 阅读