C++ 实现输出 n个不重复整数任取m个数的所有组合(附C语言实现)

野性酷女 2022-05-29 02:12 306阅读 0赞

C++** 实现输出 n个不重复整数任取m个数的所有组合(附C语言实现)**

一、简要说明

基本实现过程：先得到索引组合，再根据索引打印对应值。附C语言实现版。

二、效果图

![20180412181329182][]

![20180412181351303][]

三、例子说明

例如 6取4,声明一个数组存储索引int a\[m\];这里m=4  
例如输入：6 4  
1 2 3 4 5 6  
a\[0\]   a\[1\]     a\[2\]    a\[3\]   //所有索引组合都是递增的  
 1       2       3       4     //刚开始第一种组合 1~m  
 1       2       3       5     //最后一位不断递增，直到达到4，向左产生进位  
 1       2       3       6     //当a\[m-1\]>n 产生进位  
 1       2       4       5       
 1       2       4       6  
 1       2       5       6     //1 2 5 7 a\[3\]产生进位-》 1 2 6 7-》a\[2\]产生进位-》 1 3 6 7 调整-》1 3 4 5  
 1       3       4       5    //进位之后,后面调整为递增顺序（所有索引组合都是递增的）  
 1       3       4       6  
 1       3       5       6  
 1       4       5       6  
 2       3       4       5  
 2       3       4       6  
 2       3       5       6  
 2       4       5       6

3       4       5       6    //最后一种组合 n-m+1~n  当a\[0\]==n-m+1时遍历结束

四、实现代码

#include <iostream>
    #include <memory.h>
    #include <vector>
    using namespace std;
    
    int main()
    {
    	vector<int> arr;  //用来存储索引集合
    	int n = 0,m = 0,num = 0;
    	cin>>n>>m;
    	
    	if(m>n || m<1) return -1; //确保n>=m>=1
    	
    	//m = m>n-m? n-m:m;
    	
    	for(int i=1;i<=n;i++)//填充索引
    	{
    		cin>>num;
    		arr.push_back(num);
    	}
    	
    	vector<int> a;//用来存储每次算法产生的当前组合
    	for(int i=0;i<m;i++)//第一种组合，a[0]=1,a[1]=2,...a[m-1]=m;
    	{
    		a.push_back(i+1);
    	}
    	
    	for(int j=m;a[0]<=(n-m+1);)//当组合为最后一组时，循环结束；即a[0]=n-m+1,...,a[m-1]=n;j用来判断进位，以及进位之后的调整
    	{
    		
    		for(;a[m-1]<=n;a[m-1]++)//最后一位不断递增，直到达到最大值，产生进位
    		{
    			for(int t=0;t<m;t++)
    			{
    				cout<<arr[a[t]-1]<<'\t';
    				
    			}
    			cout<<endl;
    			
    		}
    		
    		for(j=m-2;j>=0;j--)//判断a[1]--a[m-2]是否有进位 如果 a[m-1]>n 产生进位
    		{
    			a[j]++;
    			if(a[j]<=(j+n-m+1))//a[j]不进位,那么a[j-1]也不进位，结束继续判断
    			{
    				break;
    			}
    		}
    		
    		for(j++;j>0 && j<m;j++)//调整，使得a[index-1],a[index],a[index]顺序排列，其中a[index]产生进位
    		{
    			a[j] = a[j-1]+1;
    		}
    	}
    	
    	
    	cin.get();
    	return 0;
    }

附：C语言实现方式

#include <stdio.h> 
    #include <stdlib.h>
    
    int combine(int n, int m);
    
    int main(int argc, char *argv[])
    {
    	combine(6, 4); 
    	return 0;
    }
     
    int combine(int n, int m)//从n个选m个 
    {
    	int i, j, t;
    	int *arr = (int*) malloc(sizeof(int)*n);//用来存储索引集合
    	
    	if(m>n || m<1) 
    	{
    		return -1; //确保n>=m>=1
    	}
    	
    	for(i=1;i<=n;i++)//填充索引
    	{
    		arr[i-1] = i;
    	}
    	
    	int *a = (int*)malloc(sizeof(int)*m);//用来存储每次算法产生的当前组合
    	for(i=0;i<m;i++)//第一种组合，a[0]=1,a[1]=2,...a[m-1]=m;
    	{
    		a[i] = i+1;
    	}
    	
    	for(j=m;a[0]<=(n-m+1);)//当组合为最后一组时，循环结束；即a[0]=n-m+1,...,a[m-1]=n;j用来判断进位，以及进位之后的调整
    	{
    		
    		for(;a[m-1]<=n;a[m-1]++)//最后一位不断递增，直到达到最大值，产生进位
    		{
    			for(t=0;t<m;t++)
    			{
    				printf("%d\t",arr[a[t]-1]);
    				
    			}
    			printf("\n");
    			
    		}
    		
    		for(j=m-2;j>=0;j--)//判断a[1]--a[m-2]是否有进位 如果 a[m-1]>n 产生进位
    		{
    			a[j]++;
    			if(a[j]<=(j+n-m+1))//a[j]不进位,那么a[j-1]也不进位，结束继续判断
    			{
    				break;
    			}
    		}
    		
    		for(j++;j>0 && j<m;j++)//调整，使得a[index-1],a[index],a[index]顺序排列，其中a[index]产生进位
    		{
    			a[j] = a[j-1]+1;
    		}
    	}
    	
    	free(arr);
    	free(a);
    	
    	getchar();
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmZlaWJ1eWk_size_16_color_FFFFFF_t_70][]

[20180412181329182]: /images/20220529/2523833c573e452c96046e55b5011ffe.png
[20180412181351303]: /images/20220529/e5ccfd81f36042c6b5b120e9c9fbdcde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmZlaWJ1eWk_size_16_color_FFFFFF_t_70]: /images/20220529/bf363d8de38b4ad2b17b164f115213a0.png