C++ 排列和组合（概念、例子、C++程序）

排列和组合是数学中物体的排列方式。

排列 − 在排列中，顺序很重要。因此，物体的特定顺序排列称为排列。

排列有两种类型 −

重复排列

假设我们要制作一个三位数的代码。一些可能的数字是123、897、557、333、000和001。那么我们可以制作多少个这样的数字呢？

让我们这样看待它−

在个位数上，我们有十个选项− 0-9

同样，在十位数和百位数上，我们也有十个选项。0-9.

因此，我们总共有10 * 10 * 10 = 1000个选项。

因此，我们可以制作1000个不同的重复数字排列。

泛化− 如果我们有n种选择，需要填充r个位置，我们可以制作n * n * n …（r次）个排列。

因此，带有重复的排列数量的公式是nr。

不重复排列

现在，我们需要制作一个没有数字重复的三位数代码。

例如，123、019、345、876等。

在个位数上，我们有十个选择− 0-9。

在十位数上，我们有九个选择− 0-9（不包括个位数）。

在百位数上，我们有八个选择。

因此，我们总共有8 * 9 * 10个选择。

阶乘

数的阶乘是指小于或等于该数的所有正整数的乘积。

它以数后的感叹号符号表示。

例如−

1! = 1.
2! = 2*1 = 2.
3! = 3*2*1 = 6.
4! = 4*3*2*1 = 24.
OR 
4! = 4*3! = 24
Hence n! = n*(n-1)!

现在，如果我们想计算10×9×8，可以表示为−

\frac{10!}{\lgroup 10-3\rgroup!}=\frac{10!}{7!}

=\frac{10×9×8×7!}{7!}

=10×9×8

因此，我们可以将无重复排列的数字表示为−

\frac{n!}{\lgroup n-r\rgroup!}

其中，我们需要在总共 n 个物品中选择 r 次。

符号表示

P\lgroup n,r\rgroup = nPr = nPr = \frac{n!}{\lgroup n-r\rgroup!}

要记住的要点

• nP0 = 1

• nP1 = n

• nPn-1 = n!

组合

在组合中，我们选择物品，顺序无关紧要。我们可以理解组合为从总共n个物品中无重复地选取k个物品。

示例

Consider that we want to place ‘123’ in some order.
The possibilities are 123, 132, 321, 312, 213, and 231.
That is, there are 3! = 3*2*1 = 6 possibilities.

现在，如果顺序不重要，只有一种可能性，那就是选择全部三个“123”并选择它们。

公式

因此，我们调整排列公式，将其减少多少种对象可以按顺序排列（因为我们不再关心它们的顺序）−

\frac{n!}{r!\lgroup n-r\rgroup!}

其中n是要选择的物品数，r是我们选择的物品数。顺序无关紧要，不允许重复。

符号

C\lgroup n,r\rgroup = nCr = nCr=\frac{n!}{r!(n-r)!}

示例问题

Q1. 在MISSISSIPPI的字母的不同排列中，有多少个排列不包含四个‘I’在一起？

解决方案

Given word: – MISSISSIPPI
M – 1
I – 4
S – 4
P – 2
Number of permutations = 11!/(4! 4! 2!) = (11 × 10 × 9 × 8 × 7 × 6 × 5 × 4!)/ (4! × 24 × 2)
= 34650
Now, we will remove the permutations in which the four ‘I’(s) come together.
We take that 4 I’(s) come together, and they are treated as 1 letter,
∴ Total number of letters=11 – 4 + 1 = 8
⇒ Number of permutations = 8!/(4! 2!)
= (8 × 7 × 6 × 5 × 4!)/ (4! × 2)
= 840
Therefore, the total number of permutations where four 'I'(s) don’t come together = 34650 – 840 = 33810

Q2. 一个小组由4个女孩和7个男孩组成。如果团队满足以下条件，那么有多少种方式可以选择一支由5个成员组成的团队：

• 没有女孩

• 至少有一个男孩和一个女孩

• 至少有三个女孩

解决方案

Given,
Number of girls = 7
Number of boys = 7

• 没有女孩

Total number of ways the team can have no girls = 4C0 × 7C5
= 1 × 21
= 21

• 至少一个男孩和一个女孩

1 boy and 4 girls = 7C1 × 4C4 = 7 × 1 = 7
2 boys and 3 girls = 7C2 × 4C3 = 21 × 4 = 84
3 boys and 2 girls = 7C3 × 4C2 = 35 × 6 = 210
4 boys and 1 girl = 7C4 × 4C1 = 35 × 4 = 140
Total number of ways the team can have at least one boy and one girl 
= 7 + 84 + 210 + 140
= 441

• 至少有三个女孩。

Total number of ways the team can have at least three girls = 4C3 × 7C2 + 4C4 × 7C1
= 4 × 21 + 7
= 84 + 7
= 91

要找出排列和组合，我们需要找出该数字的阶乘。因此，下面给出了找到一个数的阶乘的函数− 当前函数的阶乘数 如下所示−

//Function to find the factorial of a number.
int factorial(int n) {
   if (n == 0 || n == 1){
      return 1;
   }
   //Recursive call
   return n * factorial(n - 1);
}

例子

C++程序用于找到没有重复的排列数

现在我们可以利用上面的函数和公式来计算排列和组合 –

#include <bits/stdc++.h>
using namespace std;
//Function to find the factorial of a number.
int factorial(int n) {
   if (n == 0 || n == 1){
       return 1;
   }
   //Recursive call
   return n * factorial(n - 1);
}
//Driver Code
int main() {
   int n = 4, r = 2;
   //Calculating the combinations using the formula
   int combinations = factorial(n) / (factorial(r) * factorial(n-r));
   cout << "The number of Combinations is : " << combinations<<endl;
   //Calculating the permutations using the formula
   int permutations = factorial(n) / factorial(n-r);
   cout << "The number of Permutations is : " << permutations<<endl;
   return 0;
}

输出

对于输入n=4，r=2，上述C++程序将产生以下输出-

The number of Combinations is : 6
The number of Permutations is : 12

结论

在本文中，我们了解了排列和组合的概念。我们看到了公式、符号以及一些例子和样例问题。最后，我们还看到了C++程序。