递归（四）：组合

r囧r小猫 2021-11-24 00:24 213阅读 0赞

排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

排列与组合在日常生活中应用较广，比如在考虑某些事物在某种情况下出现的次数时，往往需要用到排列和组合。

**【例1】取值组合。**

有一个集合拥有m个元素\{1，2，…，m\}，任意的从集合中取出n个元素，则这n个元素所形成的可能子集有哪些？

假设有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\}。

编写一个程序，输入整数m和n，输出m个元素中，取出n个元素的各种情况。

（1）编程思路。

用递归程序来解决问题。

从m个数中，取出n个数的所有组合。设m个数已存于数组A\[1..m\]中。为使结果唯一，可以分别求出包括A\[m\]和不包括A\[m\]的所有组合。即包括A\[m\]时，求出从A\[1..m-1\]中取出n-1个元素的所有组合（子问题，递归）；不包括A\[m\]时，求出从A\[1..m-1\]中取出n个元素的所有组合（同样是子问题，递归）。

（2）源程序。

\#include <iostream>

using namespace std;

\#define MAXSIZE 20

void nkcombination(int i,int k,int j,int a\[\],int b\[\])

// 从n（a\[0\]）个数中连续取出k个数的所有组合，n个数已存入数组A中。

// i为待取数在数组A中的下标，j为结果数组B中的下标。

if (k==0)

for (int p=1;p<=b\[0\];p++)

cout<<b\[p\]<<" ";

cout<<endl;

else if (i+k-1<=a\[0\])

b\[j\]=a\[i\];     j++;

nkcombination(i+1,k-1,j,a,b);

// 包括A\[i\]时，递归求出从A\[i+1..n\]中取出k-1个元素的所有组合

nkcombination(i+1,k,j-1,a,b);

// 不包括A\[i\]时，递归求出从A\[i+1..n\]中取出k个元素的所有组合

int main()

int set\[MAXSIZE\],result\[MAXSIZE\];

int m,n,i;

cout<<"输入给定元素个数 m ：";

cin>>m;

for (i=1;i<=m;i++)

set\[i\]=i;

cout<<"输入取出元素个数 n：";

cin>>n;

set\[0\]=m;     result\[0\]=n;

nkcombination(1,n,1,set,result);

return 0;

**【例2】选数。**

已知n个整数x1，x2，…，xn，以及一个整数k（k＜n）。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4，k＝3，4个整数分别为3，7，12，19时，可得全部的组合与它们的和为：3＋7＋12=22，3＋7＋19＝29，7＋12＋19＝38，3＋12＋19＝34。编写一个程序计算出和为质数的组合共有多少种。

例如上例，只有一种组合的和为质数：3＋7＋19＝29。

（1）编程思路。

本例是求从n个数中选k个数的组合，并使其和为素数。求解此题时，先按例1的方法生成k个数的组合，再判断k个数的和是否为质数，若为质数则输出和式并计数。

（2）源程序。

\#include <iostream>

\#include <cmath>

using namespace std;

\#define MAXSIZE 20

int cnt=0;

bool isPrime(int num)

int m;

if(num==2) return true;

for(m=2;m<=(int)sqrt((double)num);m++)

if (num%m==0)

return false;

return true;

void nkcombination(int i,int k,int j,int a\[\],int b\[\])

if (k==0)

int p,s;

for (p=1,s=0;p<=b\[0\];p++)

s=s+b\[p\];

if (isPrime(s))

cnt++;

for (p=1;p<b\[0\];p++)

cout<<b\[p\]<<" + ";

cout<<b\[p\]<<"="<<s<<endl;

else if (i+k-1<=a\[0\])

b\[j\]=a\[i\];  j++;

nkcombination(i+1,k-1,j,a,b);

nkcombination(i+1,k,j-1,a,b);

int main()

int set\[MAXSIZE\],result\[MAXSIZE\];

int n,k,i;

cout<<"输入给定整数的个数 n ：";

cin>>n;

cout<<"依次输入"<<n<<"个整数：";

for (i=1;i<=n;i++)

cin>>set\[i\];

cout<<"输入取出元素个数 k：";

cin>>k;

set\[0\]=n;     result\[0\]=k;

nkcombination(1,k,1,set,result);

cout<<"Count="<<cnt<<endl;

return 0;

**【例3】Lotto （POJ 2245）。**

**Description**

In the German Lotto you have to select 6 numbers from the set \{1,2,...,49\}. A popular strategy to play Lotto - although it doesn't increase your chance of winning - is to select a subset S containing k (k > 6) of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k=8 and S = \{1,2,3,5,8,13,21,34\} there are 28 possible games: \[1,2,3,5,8,13\], \[1,2,3,5,8,21\], \[1,2,3,5,8,34\], \[1,2,3,5,13,21\], ... \[3,5,8,13,21,34\].

Your job is to write a program that reads in the number k and the set S and then prints all possible games choosing numbers only from S.

**Input**

The input will contain one or more test cases. Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k (6 < k < 13). Then k integers, specifying the set S, will follow in ascending order. Input will be terminated by a value of zero (0) for k.

**Output**

For each test case, print all possible games, each game on one line. The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically, that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below. The test cases have to be separated from each other by exactly one blank line. Do not put a blank line after the last test case.

**Sample Input**

8 1 2 3 5 8 13 21 34

**Sample Output**

1 2 3 5 8 13

1 2 3 5 8 21

1 2 3 5 8 34

1 2 3 5 13 21

1 2 3 5 13 34

1 2 3 5 21 34

1 2 3 8 13 21

1 2 3 8 13 34

1 2 3 8 21 34

1 2 3 13 21 34

1 2 5 8 13 21

1 2 5 8 13 34

1 2 5 8 21 34

1 2 5 13 21 34

1 2 8 13 21 34

1 3 5 8 13 21

1 3 5 8 13 34

1 3 5 8 21 34

1 3 5 13 21 34

1 3 8 13 21 34

1 5 8 13 21 34

2 3 5 8 13 21

2 3 5 8 13 34

2 3 5 8 21 34

2 3 5 13 21 34

2 3 8 13 21 34

2 5 8 13 21 34

3 5 8 13 21 34

（1）编程思路。

本题的意思是要在有k个元素的集合S中任意取6个元素，并输出所有这些取值组合。

设 combine(int take\[\], int len, int count,int num\[\])为从具有len个元素的数组num中取出count个元素，并将取出的元素存放在数组a中。

为求解combine(int take\[\], int len, int count,int num\[\])，可以先在len个元素的数组num的后面取第一个元素num\[i\]放在a\[count-1\]中，所取的第一个数组元素的下标i可以是len-1,len-2,…,count-1。注意：第一个取的数组元素的下标i不能取count-2，因为后面的要取的元素均会在第一个取的元素的前面，因此最多只能取出0~count-3共count-2个不同的y元素，达不到取count个数的目的。

在将确定组合的第一个元素num\[i\]放入数组take后，有两种选择：还未确定组合的其余元素时（count>1，即还需取count-1个元素），继续递归comb(take,i,count-1,num)确定组合的其余元素，即在num\[0\]~num\[i-1\]这i个元素中取count-1个数；已确定组合的全部元素时（count==1），输出这个组合。

（2）源程序。

\#include <iostream>

using namespace std;

void combine(int take\[\], int len, int count,int num\[\])

int i,j;

for (i = len-1; i >= count-1; i--)

take\[count - 1\] = num\[i\];

if (count >1)

combine(take, i , count - 1, num);

else

for (j = 6-1; j >=0; j--)

cout<<take\[j\]<<" ";