首页 > 数学相关 > 组合数学 > 从数组中取出r个数的所有组合
2014
08-15

从数组中取出r个数的所有组合

问题

给一个数组arr,长度为n,找出从中取出r个数的所有组合。例如对于数组{1, 2, 3, 4} ,r = 2,则打印出:{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} ,{3, 4}. 也就是 组合公式C(4,2) = 6个。 假设输入的元素没有重复,取出的r个数也没有重复。

使用递归是比较容易解决,类似分治法。组合数有如下的递归关系:C(n,r) = C(n-1, r-1) + C(n-1, r)。

我们可以考虑对当前的数取还是不取,从而不断缩小问题的范围。

代码如下:

//============================================================================
// Name        : 所有组合.cpp
// Author      : Coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : Hello World in C++, Ansi-style
//============================================================================

#include 
#include 
using namespace std;

void print(int arr[],int s,int e){
	for(int i=s; i<=e; i++){
		printf("%d ", arr[i]);
	}
	puts("");
}
/*
 arr[] 输入数组, data[]保存当前的组合
  start, end 剩余数组的起始位置
  index 已经找到的组合数的个数
  r 总共需要的组合数的个数
  */
void printAllCombination(int arr[],int data[],int start, int end,int index , int r){
	//组合够r个就打印,并返回
	if(index == r ){
		for(int i=0; i<r; i++)
			printf("%d ", data[i]);
		puts("");
		return;
	}
	//如果剩下的数组不够(r-index)个就直接返回。
	if(start + (r-index) > end ) return;
	data[index] = arr[start];//记录当前数据
	printAllCombination(arr,data ,start+1, end, index+1, r);
	printAllCombination(arr, data,start+1, end, index, r);
}
int main() {
	int arr[] = {1,2,3,4,5};
	int r = 3;
	int * data = new int[r];//保持组合数
	printAllCombination(arr,data, 0, sizeof(arr)/sizeof(arr[0]) ,0 ,r);
	return 0;
}

  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。