生成{1,2,..n}的字典序r-组合算法

递归法：

效率较低

#include<cstdio>
#include<iostream>
using namespace std;
#define ARRAYSIZE 8
#define PICKNUM 4
int gl_i = 0;//统计组合数
//对于输入inputArray[i...ARRAYSIZE-1]，取k个元素的所有组合，逆序存入outputArray中
void Recur_Combination(int inputArray[], int i, int k, int outputArray[])
{
	if (k == 0)
	{
		for (int j = 0; j < PICKNUM; j++)
		{
			cout << outputArray[j] << " ";
		}
		gl_i++;
		cout << endl;
	}
	else if (i + k - 1 <= ARRAYSIZE - 1)
	{
		outputArray[k - 1] = inputArray[i];
		//选取inputArray中第i个元素放入组合，则在剩下的inputArray[i+1..ARRAYSIZE-1]中，选取k-1个
		Recur_Combination(inputArray, i+1, k-1, outputArray);
		//若没有选取第i个元素，则在剩下的inputArray[i+1..ARRAYSIZE-1]中，选取k个
		Recur_Combination(inputArray, i+1, k, outputArray);
	}	
}
int main(int argc, char* argv[])
{
	int inputArray[ARRAYSIZE] = {1, 2, 3, 4, 5, 6, 7, 8};
	int outputArray[PICKNUM];
	//递归方法求组合
	Recur_Combination(inputArray, 0, PICKNUM, outputArray);
	cout << endl << gl_i << endl;
	return 0;
}

非递归的方法：

效率高

#include<iostream>
using namespace std;
int sum = 0;
void print(int *pickarray,int ipick)
{
	for (int i = 1; i <= ipick; i++)
		printf("%d ", pickarray[i]);
	printf("\n");
	sum++;
}
bool iscombinationover(int *pickarray, int ipick,int itotal)
{
	for (int i = 1; i <= ipick; i++)
		if (pickarray[i] != itotal - ipick + i) return false;
	return true;
}
void getcombination(int itotal, int ipick)
{
	int *pickarray = new int[ipick+1];
	for (int i = 1; i <= ipick; i++)
		pickarray[i] = i;
	print(pickarray, ipick);
	while (!iscombinationover(pickarray, ipick, itotal))
	{
		for (int i = ipick; i >= 1; i--)
		{
			if (pickarray[i] < itotal - ipick + i) {
				pickarray[i] += 1;
				for (int j = i + 1; j <= ipick; j++)
					pickarray[j] = pickarray[j - 1] + 1;
				print(pickarray, ipick);
				break;
			}
		}
	}
}
int main()
{
	int i, j;
	cin >> i >> j;
	getcombination(i, j);
	cout << sum << endl;
	system("pause");
}