Làm thế nào để bạn in tất cả các kết hợp trong python?

Đây là Chương trình Python để chấp nhận ba chữ số riêng biệt và in tất cả các kết hợp có thể có từ các chữ số

Mô tả vấn đề

Chương trình lấy ba số riêng biệt và in tất cả các kết hợp có thể có từ các chữ số

Giải pháp vấn đề

1. Lấy số thứ nhất, thứ hai và thứ ba và lưu trữ nó trong các biến riêng biệt
2. Sau đó nối cả ba số vào danh sách
3. Sử dụng ba vòng lặp for và in các chữ số trong danh sách nếu không có chỉ số nào của chúng bằng nhau
4. Lối ra

Chương trình/Mã nguồn

Đây là mã nguồn của Chương trình Python để chấp nhận ba chữ số riêng biệt và in tất cả các kết hợp có thể có từ các chữ số. Đầu ra chương trình cũng được hiển thị bên dưới

Tổ hợp là một loại sắp xếp của một số đối tượng nhất định. Về mặt 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

Trong hướng dẫn này, bạn sẽ học

Ví dụ: bạn được đưa cho 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= Đỏ, G= Lục, Y= Vàng, B= Lam, I= Chàm). Vì vậy, mẫu khả thi có thể là RGB, RGY, v.v.

Hãy quan sát hình sau

Giải trình

• 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 toán tổng số kết hợp chúng ta có thể thực hiện. Một 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

Dấu hiệu ". ” có nghĩa là giai thừa. 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ì vậy, r = 3. Sau khi tính toán, chúng tôi nhận được,

Có thể kết hợp tổng cộng 10 màu cho trường hợp trên

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

Bây giờ, giả sử, cho một mảng 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 kích thước n thì sẽ mất O(n2) thời gian để thực hiện tác vụ. Ngoài ra, nếu chúng tôi muốn xóa mục nhập 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 một 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, tổng thời gian phức tạp trở thành = O(n2) + O(nLog(n)). Chúng ta có thể coi nó là O(n2), vì n2 lớn hơn nhiều so với n*log(n)

Phương pháp-1. Phần tử cố định với đệ quy

Trong phương pháp này, chúng tôi sẽ chọn một phần tử sau đó tìm tổ hợp của r-1 phần tử. 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 chứng minh từng bước thuật toán bằng sơ đồ

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

Bước 1) Trong lớp đầu tiên, lấy n-r+1 phần tử. 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à nâng nó lên n-r. 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 phần

Hình trên là giá trị trả về từ đệ quy. Chỉ 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 trong 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 bằng 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

Phương pháp 2 (Bao gồm và Loại trừ mọi phần tử)

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

Theo danh tính 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 của r phần tử từ một mảng có kích thước n đã cho

1. Phần tử được bao gồm trong Tổ hợp hiện tại
2. Phần tử bị loại trừ khỏi 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 trong 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 bằng Python

đầ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 có mặt 2 lần
• Bây giờ, nếu chúng ta muốn chạy mã cho mảng này, một số 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 chứa 5, sẽ được lặp lại

Chúng ta có thể sử dụng hai phương pháp này

• 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 giống nhau. Về cơ bản, đặt hai dòng mã sau vào chức năng Kết hợp

#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);
}

#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);
}

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

Vì vậy, nếu chúng tôi không muốn sắp xếp các thành phần để theo dõi trùng lặp, chúng tôi 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 Tổ hợp đã tạo vào hashmap 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à các giá trị
Bước 3) khi chức năng chạy xong, 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

#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

#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);
}

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 khi chúng tôi sử dụng từ điển và coi mỗi Tổ hợp là khóa, chúng tôi chỉ có thể in 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

#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);
}

Vì vậy, chúng ta có thể thấy rằng RGB, RYB, GYB đã xảy ra 2 lần. Độ phức tạp về 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ì tổng thời gian phức tạp để 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 tôi cần O(n*log(n)) để sắp xếp; . Tổng thời gian phức tạp sẽ là

Làm cách nào để in tất cả các kết hợp có thể có của một số trong Python?

Làm cách nào để in tất cả các kết hợp có thể có của một chuỗi trong Python?

Làm cách nào để tạo tất cả các kết hợp có thể có của các mục từ một danh sách?

Làm cách nào để có được tất cả các kết hợp có thể có của 3 số trong Python?