Hỏi về cách duyệt tổ hợp

gothammmmm · July 10, 2021, 2:42am

Em có 1 đề bài dạng như thế này: “Cho m con đường, chọn k con đường sao cho thoả mãn nhất…”
Trước khi nghĩ thuật chuẩn thì em đang định làm trâu cho subtask m <= 32 và k <= 7. Em thấy là nếu chọn k cái bất kì trong m cái thì cần mCk trường hợp thì chỉ tầm 3 triệu là ok rồi nên em đang nghĩ đến việc đệ quy rồi check nhưng có vẻ như nó quá thời gian khi em nộp, code em có dạng tựa tựa thế này:

void backtrack()
{
    if(p.size() == k)
    {
        ll res = cal() ;
        ans = max(ans, res) ;
        return ;
    }
    FOR(i, 1, m)
    {
           if(dd[i]) continue ;
           p.pb(i) ; dd[i] = 1 ;
           backtrack() ;
          p.pop_back() ; dd[i] = 0 ;
    }
}
void solve()
{
    FOR(i, 1, m)
    {
           p.pb(i) ; dd[i] = 1 ;
           backtrack() ;
           p.pop_back() ; dd[i] = 0 ;
    }
        cout << ans << ' ' ;
}

Cho em hỏi vì sao trâu đệ quy lại quá thời gian và nên làm thể nào cho chuẩn với subtask này ạ !

tntxtnt · July 10, 2021, 2:32am

C++ ko có duyệt từng tổ hợp nhưng có duyệt tất cả các chỉnh hợp, có thể sửa nó thành duyệt tổ hợp n chập k như sau:

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main() {
    // Ví dụ chuỗi "1234567" là mảng chứa n=7 ký tự, duyệt tất cả các tổ hợp với k=4
    std::string s = "1234567";
    int n = s.size();
    int k = 4;
    std::vector<int> take(n, 0);
    std::fill(begin(take), begin(take) + k, 1);
    int id = 0;
    do {
        std::cout << ++id << ": ";
        for (int i = 0; i < n; ++i)
            if (take[i]) std::cout << s[i];
        std::cout << "\n";
    } while (std::prev_permutation(begin(take), end(take)));
}

hơi rắc rối tí :V :V

Hàm std::next_permutation hay std::prev_permutation cho mảng chứa n phần tử khác nhau đôi một sẽ duyệt n! lần (chỉnh hợp của n phần tử đó). Ví dụ mảng {0,1,2,3} nó sẽ duyệt 4! = 24 lần từ 0123 tới 3210 với next_permutation và từ 3210 về 0123 với prev_permutation.

Nếu có m phần tử trùng nhau trong n phần tử thì nó chỉ duyệt \dfrac{n!}{m!} lần (bỏ qua m! lần trùng nhau).

Vậy để nó duyệt đúng tổ hợp n chập k = \dfrac{n!}{k!(n-k)!} thì ta cần tạo tập hơn n phần tử với k phần tử giá trị 1 (chọn nên lấy giá trị là 1) và n-k phần tử giá trị 0 (ko chọn):

    std::vector<int> take(n, 0); // mảng n phần tử 0
    std::fill(begin(take), begin(take) + k, 1); // gán 1 cho k phần tử đầu tiên

rồi duyệt prev_permutation để nó duyệt từ 11...100...0 về 00...011...1. Cuối cùng để lấy các phần tử trong mảng cần lấy n chập k thì ta ktra nếu take[i] thì s[i] sẽ được chọn.

gothammmmm · July 10, 2021, 3:48am

cách này em hiểu rồi nhưng em nghĩ là với số lớn thì next_permutation sẽ mất n! độ phức tạp sẽ quá thời gian ý ạ ?
vì subtask ở đây là m <= 32 thì cơ bản việc next_permutation của 32 đã quá thời gian rồi. Em nghĩ next_permutation chỉ hợp với m <= 10, còn với m <= 20 thì sinh nhị phân là ok qua. Nhưng với m <= 32 thì em đang thắc mắc

tntxtnt · July 10, 2021, 11:12am

m=32 mà k=7 duyệt cách trên cũng được mà :V Nó ko xét 32! trường hợp đâu, chỉ xét khoảng \dfrac{32!}{7! \times 25!} thôi :V

a chạy đếm thử C(32, 7) hơn 3tr trường hợp có 0.05s nè tức là nó ko duyệt 32! đâu. Thư viện chuẩn người ta cũng khôn lắm chứ =]

gothammmmm · July 10, 2021, 3:42pm

dạ vâng em cảm ơn anh ạ ! <3