组合算法：打印 R 的所有可能组合

何谓组合？

组合是一些给定对象的一种排列。从数学术语上讲，组合是从一组独特的项目/对象中进行的一组选择。在这里，项目的顺序并不重要。它也被称为计算事件总结果的方法，其中结果的顺序并不重要。

例如，给你一个装有 5 种不同颜色的袋子，要求你用任意 3 种颜色拼出一个图案。你也可以从 3 种颜色中任意挑选 4 种颜色，然后按不同的顺序排列它们。

假设颜色为 RGYBI（R= 红色、G= 绿色、Y= 黄色、B= 蓝色、I= 靛蓝）。因此，可能的模式可以是 RGB、RGY 等。

我们来看看下面的图：

说明：

从 4 种颜色中任意选出 5 种并列出
从每个 4 种颜色块中，选择任意 3 种并全部列出。例如，我们在图中仅选择了“RGBI”，并显示了 4 种组合。
有一种理论可以计算我们可以做出的组合总数。n 个元素中的 r 个元素的组合可以用数学表示为：

标志 “！” 意思是阶乘。例如，
不！ = N * (N-1) * (N-2) * … * 3 * 2 * 1
比如说，5！= 5*4*3*2*1 = 120

因此，对于上述问题，我们有 5 种颜色，即 n = 5，在任何给定时间，我们需要选择任意 3 种。因此，r = 3。经过计算，我们得到，

上述场景总共可能有 10 种颜色组合。

组合的时间复杂度分析

现在，假设给定一个大小为 n 的数组，要求我们从数组中取出 r 个元素并执行 r 个元素的组合。

如果给定一个大小为 n 的数组，则需要 O(n²）执行任务的时间。此外，如果我们想删除重复的条目，那么，

我们需要执行以下步骤：

步骤1） 对输入数组数据按升序排序。排序的时间复杂度为 O（n*log（n））。

步骤2） 根据给定的临时数组数据创建另一个包含唯一元素的数组。

步骤3） 然后，执行组合功能。

因此，总时间复杂度变为= 上²）+ O（nLog（n））。 我们可以认为它为 O(n²)，作为²远大于 n*log(n)。

方法 1：使用递归固定元素

在这个方法中，我们会选择一个元素，然后找到 r-1 个元素的组合。当我们从其余元素中选择一个元素时，我们会以递归方式进行，这就是为什么它被称为固定元素和递归。

我们通过图表一步一步地演示一下该算法：

步骤如下：

步骤1） 在第一层，取 n-r+1 个元素。也就是说，我们取了 3 个元素。

步骤2） 从第二层中选取一个元素并将其向上移动到 nr。因此，如果我们取“R”，那么通过 R，我们可以取 G、Y 和 B。

步骤3） 从第 3 层选取一个元素并将其带到第 n 个元素，并形成每个包含 3 个元素的块。

上图是递归的返回值。仅打印最后一层。

伪代码

function combination:
pass in: inputArray, combinationArray, start, end, index, r
if index is equal to r:
for each element in combinationArray:
print each element
return
for i = start:
if i <=end and end -i+1 > r-index:
combinationArray[index] = inputArray[i]
call combination function again with updated parameter

在 C/ 中实现C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int start, int end, int index, int r) {
  if (index == r) {
    for (int i = 0; i & lt; r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i & lt; = end & amp; & amp; end - i + 1 & gt; = r - index; i++) {
    combinationArray[index] = inputArray[i];
    Combination(inputArray, combinationArray, i + 1, end, index + 1, r);
  }
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, 0, n - 1, 0, r);
}

输出：

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

在实施 Python

def Combination(inputArray, combinationArray, start, end, index, r):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
i = start
while (i & lt; = end and end - i + 1 & gt; = r - index):
    combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, i + 1, end, index + 1, r)
i += 1
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [0] * r
Combination(inputArray, combinationArray, 0, n - 1, 0, r)

输出：

R G Y 
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

方法 2（包含和排除每个元素）

此方法基于 Pascal 恒等式。之前我们使用递归来计算 nCr。这里，方法只是除法，而不是复杂的循环。

根据帕斯卡的身份，

nCr = (n-1)Cr + (n-1)C(r-1)

因此，递归算法将有 2 个递归逻辑来从给定的大小为 n 的数组中找到 r 个元素的组合。

元素包含在当前组合中
元素已从当前组合中排除

伪代码

function combination:
pass in: inputArray, combinationArray, n, r, index, i
if the index is equal to r:
for each element in combination array:
print each element
if i>=n:
return
  combinationArray[index] = inputArray[i]
  combination(inputArray, combinationArray, n, r, index+1, i+1)
  combination(inputArray, combinationArray, n, r, index, i+1)

在 C/ 中实现C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int n, int r, int index, int i) {
  if (index == r) {
    for (int j = 0; j & lt; r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i & gt; = n)
    return;
  combinationArray[index] = inputArray[i];
  Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
  Combination(inputArray, combinationArray, n, r, index, i + 1);
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, n, r, 0, 0);
}

输出：

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

在实施 Python

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)

输出：

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

处理重复组合

有时输入数组中可能会有重复的元素。

例如，

输入数组包含 n = {5, 2, 3, 1, 5}。
这里我们可以看到 5 出现了 2 次。
现在，如果我们要运行这个数组的代码，一些组合将会重复。
我们会发现 {5, 2, 5}、{5, 2, 3} 等或任何包含 5 的组合都会重复。

我们可以使用这两种方法：

对输入数组进行排序。排序将花费 O(nlog(n)) 时间。
然后增加i的值，同时i值和i+1的值相同。基本上将以下两行代码放在Combination函数中。

// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

使用字典或无序映射来跟踪重复的组合

因此，如果我们不想对元素进行排序以跟踪重复项，我们可以按照给定的步骤进行操作。

步骤1） 声明一个全局字典或者哈希图。
步骤2） 将生成的组合推送到哈希表中，并将值加一。组合是键，它们的出现是值。
步骤3） 当函数运行完成后，我们只需打印哈希图或字典中的所有键。

以下是 Python 中的实现

unique_combination = dict()
def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    temp_combination = ""
for item in combinationArray:
    temp_combination += item
unique_combination[temp_combination] = unique_combination.get(temp_combination, 0) + 1
return
if i & gt; = n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBIB"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)
for item in unique_combination.keys():
    print(item)

输出：

RGY
RGB
RGI
RYB
RYI
RBI
RBB
RIB
GYB
GYI
GBI
GBB
GIB
YBI
YBB
YIB
BIB

在这里，您可以看到输入是“RGYBIB”。通常，应该会出现一些重复的组合。但由于我们使用了字典并将每个组合视为键，因此我们只能打印唯一的组合。

现在，如果你输入“print(unique_combination)”，你可以看到每个组合的频率。它将显示如下：

{'RGY': 1, 'RGB': 2, 'RGI': 1, 'RYB': 2, 'RYI': 1, 'RBI': 1, 'RBB': 1, 'RIB': 1, 'GYB': 2, 'GYI': 1, 'GBI': 1, 'GBB': 1, 'GIB': 1, 'YBI': 1, 'YBB': 1, 'YIB': 1, 'BIB': 1}

因此，我们可以看到 RGB、RYB、GYB 出现了 2 次。将键插入字典的时间复杂度基本上是 O(1)。因此，如果使用字典，则运行代码的总时间复杂度将是：

O(1) + O(n*n)

相当于O(n*n)。

使用之前的方法跟踪重复项，排序需要 O(n*log(n))；比较需要 O(n)，函数本身需要 O(n*n)。总时间复杂度为：

O（n*log（n））+O（n）+O（n*n）

何谓组合？

组合的时间复杂度分析

方法 1：使用递归固定元素

伪代码

在 C/ 中实现C++

在实施 Python

相关文章

方法 2（包含和排除每个元素）

伪代码

在 C/ 中实现C++

在实施 Python

处理重复组合

使用字典或无序映射来跟踪重复的组合

以下是 Python 中的实现

注册简报