Thuật toán kết hợp: In tất cả các kết hợp có thể có của R

Bởi: Sarah Chen Sarah Chen
Hours cập nhật

Sự kết hợp là gì?

Sự kết hợp là một kiểu sắp xếp của một số đối tượng nhất định. Theo thuật ngữ toán học, Kết hợp là một tập hợp các lựa chọn/lựa chọn các mục từ một tập hợp các mục/đối tượng duy nhất. Ở đây, thứ tự của các mục không quan trọng. Nó còn được gọi là phương pháp tính tổng kết quả của một sự kiện, trong đó thứ tự của kết quả không quan trọng.

Ví dụ: bạn được tặng một chiếc túi có 5 màu khác nhau và được yêu cầu tạo một mẫu có 3 màu bất kỳ. Bạn cũng có thể chọn 3 màu bất kỳ trong số 4 màu, sau đó sắp xếp chúng theo thứ tự khác nhau.

Giả sử các màu là RGYBI(R= Red, G= Green, Y= Yellow, B= Blue, I= Indigo). Vì vậy, mẫu có thể có có thể là RGB, RGY, v.v.

Chúng ta hãy cùng xem hình sau:

Sự kết hợp màu sắc
Sự kết hợp màu sắc

Giải thích:

  • Lấy 4 màu bất kỳ trong số 5 màu và liệt kê chúng
  • Từ mỗi khối 4 màu, chọn 3 màu bất kỳ và liệt kê tất cả. Ví dụ: chúng tôi chỉ chọn “RGBI” trong hình và hiển thị 4 kết hợp.
  • Có một lý thuyết đằng sau nó để tính tổng số kết hợp mà chúng ta có thể thực hiện. Sự kết hợp của r phần tử trong số n có thể được biểu diễn dưới dạng toán học:
Công thức kết hợp

Công thức kết hợp

Dấu hiệu "!" có nghĩa là những yếu tố. Ví dụ,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Nói, 5! = 5*4*3*2*1 = 120

Vì vậy, đối với bài toán trên, chúng ta có 5 màu nghĩa là n = 5 và tại bất kỳ thời điểm nào, chúng ta cần chọn 3 màu bất kỳ. Vậy r = 3. Sau khi tính toán, chúng ta nhận được:

Kết hợp

Có thể kết hợp tổng cộng 10 màu cho kịch bản trên.

Phân tích độ phức tạp thời gian cho Kết hợp

Bây giờ, giả sử, cho một mảng có kích thước n, chúng ta được yêu cầu lấy r phần tử từ mảng và thực hiện kết hợp r phần tử.

Nếu cho trước một mảng có kích thước n thì nó sẽ mất O(n2) thời gian thực hiện nhiệm vụ. Ngoài ra, nếu chúng tôi muốn loại bỏ mục trùng lặp, thì:

Chúng ta cần thực hiện các bước sau:

Bước 1) Sắp xếp dữ liệu mảng đầu vào theo cách tăng dần. Độ phức tạp thời gian của việc sắp xếp là O(n*log(n)).

Bước 2) Tạo một mảng khác chứa phần tử duy nhất từ ​​dữ liệu mảng tạm thời đã cho.

Bước 3) Sau đó, thực hiện chức năng kết hợp.

Vì vậy, độ phức tạp thời gian tổng thể trở thành = Trên2) + O(nLog(n)). Chúng ta có thể coi nó là O(n2), như n2 lớn hơn nhiều so với n*log(n).

Cách 1: Phần tử cố định có đệ quy

Trong phương pháp này, chúng tôi sẽ chọn một phần tử sau đó tìm sự kết hợp của các phần tử r-1. Khi chúng tôi chọn một phần tử từ phần tử còn lại, chúng tôi đang thực hiện đệ quy và đó là lý do tại sao nó được gọi là phần tử cố định và đệ quy.

Hãy trình diễn thuật toán từng bước bằng sơ đồ:

Phần tử cố định có đệ quy

Các bước được đưa ra dưới đây:

Bước 1) Trong lớp đầu tiên, lấy các phần tử n-r+1. Có nghĩa là chúng tôi đã lấy 3 yếu tố.

Bước 2) Chọn một phần tử từ lớp thứ 2 và đưa nó lên nr. Vì vậy, nếu chúng ta lấy “R” thì với R, chúng ta có thể lấy G, Y và B.

Bước 3) Chọn một phần tử từ lớp thứ 3 và đưa nó lên phần tử thứ n và tạo thành các khối chứa 3 phần tử, mỗi khối.

Hình trên là giá trị trả về từ đệ quy. Chỉ có lớp cuối cùng sẽ được in.

Mã giả

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

Triển khai bằng 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);
}

Đầu ra:

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

Triển khai tại 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)

Đầu ra:

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

NHỮNG BÀI VIẾT LIÊN QUAN

Cách 2 (Bao gồm và loại trừ mọi phần tử)

Phương pháp này dựa trên bản sắc của Pascal. Trước đây chúng ta sử dụng đệ quy để tính nCr. Ở đây, phương pháp chỉ được chia thay vì một vòng lặp phức tạp.

Theo nhận dạng của Pascal,

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

Vì vậy, sẽ có 2 logic đệ quy cho thuật toán đệ quy để tìm Tổ hợp r phần tử từ một mảng có kích thước n cho trước.

  1. Phần tử được bao gồm trong Kết hợp hiện tại
  2. Phần tử bị loại trừ khỏi Kết hợp hiện tại

Mã giả

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)

Triển khai bằng 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);
}

Đầu ra:

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

Triển khai tại 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)

Đầu ra:

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

Xử lý các kết hợp trùng lặp

Đôi khi có thể có các phần tử trùng lặp trong mảng đầu vào.

Ví dụ,

  • Mảng đầu vào chứa n = {5, 2, 3, 1, 5}.
  • Ở đây, chúng ta có thể thấy rằng 5 xuất hiện 2 lần.
  • Bây giờ, nếu chúng ta muốn chạy mã cho mảng này, một số kết hợp sẽ được lặp lại.
  • Chúng tôi sẽ tìm thấy {5, 2, 5}, {5, 2, 3}, v.v. hoặc bất kỳ kết hợp nào có chứa 5 sẽ được lặp lại.

Chúng ta có thể sử dụng hai phương pháp sau:

  • Sắp xếp mảng đầu vào. Việc sắp xếp sẽ mất thời gian O(nlog(n)).
  • Sau đó tăng giá trị của i, trong khi giá trị i và giá trị i+1 là như nhau. Về cơ bản, hãy đặt hai dòng mã sau vào hàm Combination.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

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

Sử dụng từ điển hoặc bản đồ không có thứ tự để theo dõi các kết hợp trùng lặp

Vì vậy, nếu không muốn sắp xếp các phần tử để theo dõi phần trùng lặp, chúng ta có thể làm theo các bước đã cho.

Bước 1) Khai báo một từ điển toàn cầu hoặc hashmap.
Bước 2) Đẩy Kết hợp đã tạo vào bản đồ băm và tăng giá trị lên một. Sự kết hợp là chìa khóa và sự xuất hiện của chúng là giá trị.
Bước 3) khi hàm chạy xong, chúng ta chỉ cần in tất cả các khóa từ hashmap hoặc từ điển.

Đây là cách triển khai trong 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)

Đầu ra: 

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

Tại đây, bạn có thể thấy đầu vào là “RGYBIB”. Nói chung, sẽ xảy ra một số kết hợp trùng lặp. Nhưng vì chúng tôi đã sử dụng từ điển và coi mỗi Kết hợp là khóa nên chúng tôi chỉ có thể in Kết hợp duy nhất.

Bây giờ, nếu bạn viết “print(unique_combination)”, bạn có thể thấy tần suất của từng kết hợp. Nó sẽ hiển thị như thế này:

{'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}

Vì vậy, chúng ta có thể thấy RGB, RYB, GYB đã xảy ra 2 lần. Độ phức tạp thời gian của việc chèn khóa vào từ điển về cơ bản là O(1). Vì vậy, nếu bạn sử dụng từ điển, thì độ phức tạp thời gian tổng thể để chạy mã sẽ là:

O(1) + O(n*n)

Tương đương với O(n*n).

Sử dụng phương pháp trước để theo dõi trùng lặp, chúng ta cần O(n*log(n)) để sắp xếp; để so sánh, chúng ta cần O(n), và bản thân hàm mất O(n*n). Độ phức tạp thời gian tổng thể sẽ là:

O(n*log(n)) + O(n) +O(n*n)

Bạn có thể thích: