Tạo tập hợp con C++ đệ quy

Tại sao quay lui? . Nếu chúng ta thiết kế thuật toán một cách thông minh, chúng ta có thể khiến logic quay lui hoạt động cho mình và tạo ra tất cả các tập hợp con có thể

Ý tưởng là nếu chúng ta có N số phần tử bên trong một mảng, thì chúng ta có chính xác hai lựa chọn cho mỗi phần tử đó, hoặc chúng ta đưa phần tử đó vào tập hợp con của mình hoặc chúng ta không bao gồm phần tử đó. Vì vậy, chiến lược lấy hoặc không lấy sẽ xây dựng một cây nhị phân giả gồm các lựa chọn chỉ trả lại các lá cho mỗi kết hợp dẫn đến bộ quyền lực

Cây đệ quy cho ví dụ trên sẽ như thế này

các bước giải quyết

Chúng tôi chỉ có thể xây dựng tập hợp con có kích thước khác nhau trong một mảng tôi. e. tập hợp con[]. Đây là các bước để tạo ra nó

• Chọn một yếu tố từ đầu vào i. e. tập con[len] = S[pos]. Chúng tôi có thể quyết định đưa nó vào tập hợp con hiện tại hay không
• Đệ quy tạo thành tập hợp con bao gồm nó i. e. allSubsets(pos+1, len+1, subset)
• Đệ quy tạo thành tập hợp con không bao gồm nó i. e. allSubsets(pos+1, len, subsets)
• Đảm bảo tạo từng bộ một lần

Mã giả

int S[N]
void allSubsets(int pos, int len, int[] subset) 
{
  if(pos == N) 
  { 
     print(subset)
     return
  }
  // Try the current element in the subset.
  subset[len] = S[pos]
  allSubsets(pos+1, len+1, subset)
  // Skip the current element.
  allSubsets(pos+1, len, subset)
}

Phân tích độ phức tạp

Ở đây chúng tôi đang tạo mọi tập hợp con bằng cách sử dụng đệ quy. Tổng số tập hợp con của một tập hợp có kích thước n = 2^n đã cho

Thời gian phức tạp. O(2^n)

Độ phức tạp không gian. O(n) cho tập hợp con mảng bổ sung

Ý tưởng quan trọng để suy nghĩ

• Tại sao chúng ta theo dõi cả hai trường hợp khi chúng ta chọn phần tử và khi chúng ta không chọn phần tử?
• Bạn có thể viết mối quan hệ lặp lại cho thuật toán trên không?
• Bạn có thể nghĩ ra một số cách khác để thực hiện giải pháp này không?
• Chúng ta có thể giải quyết vấn đề này bằng ngăn xếp không?
• Xác định các vấn đề có thể được giải quyết bằng cách sử dụng phương pháp tương tự

2. Phương pháp mặt nạ bit

Ý tưởng giải pháp

Vì vậy, thay vì sử dụng một mảng, chúng ta chỉ có thể sử dụng một số nguyên duy nhất có các bit riêng lẻ đại diện cho các mục của mảng. Vì vậy, bit thứ i là 1 hoặc 0 vì mục nhập thứ i của mảng là đúng hay sai. Đây thường được gọi là phương pháp mặt nạ bit, thực sự hữu ích để giải quyết các loại vấn đề khác. (Nghĩ. )

Để hiểu quay lui là gì, hãy quay lại những điều cơ bản của các lệnh gọi hàm. Trong một lời gọi hàm, có hàm được gọi và hàm gọi. Vì vậy, trong đoạn mã dưới đây,

gen(A,0,sz)

là hàm gọi và

gen(vector &A,int k,int n)

là hàm được gọi

Giả sử hàm gọi nằm trong hàm chính và tất nhiên hàm được gọi được xác định bên ngoài hàm chính. Vì quá trình thực thi luôn bắt đầu từ chức năng chính, nên quá trình thực thi chương trình sẽ đến chức năng gọi trước và sau khi đạt đến, quá trình thực thi sẽ rời khỏi chức năng chính và tiếp tục thực thi trong chức năng được gọi (sử dụng trình gỡ lỗi để xem hoạt động của hành vi này). Bây giờ, khi trình biên dịch đã hoàn thành việc thực thi các mã trong hàm được gọi, điều khiển sẽ quay trở lại hàm gọi;

Giải thích ở trên có thể không mang lại sự hiểu biết đầy đủ về khái niệm này bởi vì ở đó chúng ta đã xử lý tình huống chỉ có một lệnh gọi hàm và định nghĩa hàm của hàm được gọi nằm ngoài hàm gọi

Bây giờ chúng ta hãy hiểu rõ hơn về quay lui - điều cần thiết để hiểu cách tạo tập hợp con bằng cách sử dụng đệ quy. Một hàm có khả năng gọi chính nó – hàm như vậy được gọi là hàm đệ quy. Bao nhiêu lần một chức năng có thể gọi chính nó? . Bây giờ giả sử chúng ta có một biến gọi là k được khởi tạo bằng 0 và chúng ta nói rằng một hàm sẽ tiếp tục gọi chính nó trong khi k<5. Điều đó có nghĩa là lần đầu tiên hàm gọi chính nó, k bắt đầu từ 0 trở thành 1, lần thứ hai k trở thành 2, rồi 3, rồi 4 và sau đó ở lần gọi tiếp theo, k trở thành 5 và điều kiện được thỏa mãn. Chuyện gì xảy ra tiếp theo?

//code in c++
void fun(int n, int k){
     if(k==n){
        return;
     }
     fun(n,k+1);
     cout<

Hàm được gọi fun(5,5) trả về (tại k = 5) trả về hàm gọi tại fun(5,4) và sau đó bất kỳ câu lệnh nào được viết sau khi fun(5,4) được thực thi – trong trường hợp này là giá trị . Sau đó, hàm được gọi fun(5,3) quay trở lại hàm gọi fun(5,2) và sau đó giá trị 3 được in sau 4, v.v. cho đến khi đạt đến hàm gọi fun(5,0) tại thời điểm đó chương trình . 4,3,2,1,0 để sàng lọc và sau đó điều khiển quay trở lại chức năng chính. Vì vậy, lưu ý rằng mỗi giá trị k được trình biên dịch chèn vào một ngăn xếp trong các cuộc gọi đệ quy, và sau đó trong quá trình quay lui, kết quả được in theo các giá trị của k trong ngăn xếp (do đó in ngược các giá trị k); . Sử dụng trình gỡ lỗi để xem mọi thứ hoạt động như thế nào, đảm bảo nghiên cứu ngăn xếp cuộc gọi trong khi thực hiện chương trình để xem điều gì đang xảy ra với các giá trị k tại mỗi cuộc gọi đệ quy và trong quá trình quay lui

Vì vậy, bây giờ bạn đã hiểu về quay lui, hãy bắt đầu. cách tạo tập hợp con bằng cách sử dụng quay lui đệ quy

Đối với ví dụ của chúng tôi về cách tạo các tập hợp con bằng cách sử dụng đệ quy, hãy lấy một bộ ký tự A={A,B,C} và chương trình mẫu của chúng tôi sẽ in tất cả các tập hợp con của tập hợp A,B,C cho chúng tôi; . { }, {C}, {B}, {B,C}, {A}, {A,C}, {A,B}, {A,B,C}

Chúng ta gọi hàm gen(A,k+1,n) với tham số A,K,n trong đó A là mảng ký tự của chúng ta, k đại diện cho các chỉ số của mảng A và n là kích thước của A

Triển khai mã trong c ++

#include 

using namespace std;

void gen(vector &A,int k,int n){
    static vector v;
    if(k == n){
        //print subsets
        for(auto x : v)
            cout< A = {'A','B','C'};//set of characters
    int sz = A.size();
    gen(A,0,sz);
}

Một điều tôi nên làm rõ hơn. hãy xem mã của tôi và lưu ý rằng gen(A,k+1,n) được gọi hai lần – trước khi tôi cho bạn biết lý do tại sao, trước tiên hãy để tôi nói với bạn rằng trong một hàm đệ quy có hai hoặc nhiều lệnh gọi đệ quy như thế này, ngoại trừ . Vì vậy, mã này được triển khai giống như một nhánh đầu tiên đi bên trái, sau đó đi đến nhánh bên phải của loại hàm đệ quy. Hãy xem cây đệ quy được tạo cho mã này để hiểu điều gì đang xảy ra

gen(0) ở trên cùng của cây có nghĩa là. hàm gen() được gọi đầu tiên với k giá trị 0 (cuộc gọi đó xuất phát từ hàm chính). Sau đó, gen(1) được gọi từ bên trong chính nó – bạn nên chú ý tham số k+1 trong lệnh gọi đệ quy, đó là nơi 1 xuất phát. Sau đó, hãy nhớ rằng tôi đã nói trừ khi lệnh gọi đệ quy hàm gen() đầu tiên đến trường hợp cơ sở, việc thực thi không vượt qua lệnh gọi đệ quy đầu tiên đó. Vì vậy, gen(0) gọi gen(1) trên nhánh trái của cây, gen(1) gọi gen(2), gen(2) gọi gen(3) tại điểm k == n (điều kiện cơ sở của chúng tôi). Bởi vì k == n, việc thực thi sẽ nhập câu lệnh if của chúng ta nhưng vectơ v của chúng ta chưa có giá trị nào được lưu trữ trong đó, vì vậy việc thực thi sẽ bỏ qua nó và in ra một tập hợp trống – thực tế là một phần của tập hợp con của chúng ta

Bây giờ việc thực thi đã đạt đến điều kiện cơ bản và một tập trống đã được in, quá trình thực thi quay trở lại hàm gọi trong đó giá trị k bằng 2; . Tiếp theo mã của chúng tôi phân nhánh bên phải (i. e gọi lần gọi đệ quy thứ hai – như có thể thấy trong cây đệ quy ở trên), nhưng ngay lập tức k lại trở thành 3 (trường hợp cơ sở của chúng ta); . Tại thời điểm này, chúng ta đã hoàn thành với nhánh trái và nhánh phải ở k giá trị 2, vì vậy việc thực thi quay trở lại điểm có giá trị k là 1 và giá trị của A[1] được chèn vào vectơ v của chúng ta – vì vậy bây giờ chúng ta có . Luồng thực thi tiếp tục ở nhánh bên phải của lời gọi đệ quy của chúng ta; . Thực thi nhập điều kiện cơ sở, in những gì chúng ta có trong vectơ – i. e B. Thực thi trả về chức năng gọi tại k == 2; . Việc thực thi tiếp tục ở nhánh bên phải bằng cách gọi hàm đệ quy thứ hai tại gen(3); . e {B,C}, thực thi quay trở lại hàm gọi tại k==2;

Điều tôi muốn bạn làm bây giờ là lấy bút và giấy và tiếp tục vạch ra phần còn lại của cuộc hành quyết trên giấy bút. Chỉ cần sao chép những gì tôi đã làm trong sơ đồ và bạn sẽ hiểu rõ hơn về những gì đang diễn ra. Nếu bạn làm tốt, bạn nên tạo tất cả các tập hợp con của tập hợp A={A,B,C} do đó. { }, {C}, {B}, {B,C}, {A}, {A,C}, {A,B}, {A,B,C}. Tôi đã tìm đến { }, {C}, {B}, {B,C} để chỉ cho bạn cách thực hiện, hãy tiếp tục và hoàn thành nó và cho tôi biết suy nghĩ của bạn trong phần nhận xét bên dưới

Thời gian và không gian phức tạp

Độ phức tạp về thời gian của hàm gen() là O(2n) và vì tôi đã lấy thêm một mảng nên khoảng trống thừa được lấy là O(n)