Tìm tập con đứng trước

[Star_Lucky]

Thầy giáo giao bài này mà em đang không biết làm, các anh chị giúp em với ạ!

[SITUVN.gcd]

Do bạn không hiểu đề hay đã hiểu đề nhưng chưa biết hướng làm?
Chứ mình thấy cái đề cũng khó hiểu lắm.

[nguyen2812 (Bùi Đình Nguyên)]

Đề bài hình như chưa rõ ràng về thế nào là tập con đứng trước thì phải.
2 3 5 thì tập con đứng trước là 2 3 4.
2 3 6 thì tập con là 2 3 5 hay là 2 3 4 ạ.

[rogp10]

Đứng liền trước đó bạn.

[Le_Trong1 (Lê Trọng)]

Tui suy nghĩ nổ não vẫn không hiểu cách tìm tập con trước đó là như thế nào. Hay là phải tạo một list tất cả các tập hợp con X[] có K phần tử thuộc N.

[rogp10]

Thường làm +1 thì bây giờ là -1

[phamdat2 (Phạm Tiến Đạt)]

nếu X = [1, 2, 3] thì trước đó vẫn là [1, 2, 3] chứ nhỉ

[rogp10]

Chú ý nếu tập con trong input là đầu tiên thì trước đó là tập con cuối cùng.

[tntxtnt]

C++ thì có sẵn hàm next_permutation hoặc prev_permutation :V :V

---

• next_permutation(begin(a), end(a)) sẽ tạo ra tập hợp gồm n! phần tử chính là chỉnh hợp của mảng a = \{1, 2, 3, ..., n\}
• Nếu a có 2 phần tử trùng nhau, ví dụ a = \{1, 1, 3, 4, 5, ..., n\}, thì next_permutation(begin(a), end(a)) chỉ tạo ra tập hợp có \dfrac{n!}{2!} phần tử.
• Nếu a = \{1, 1, 2, 2, 2, 6, 7, 8 ..., n\}, thì next_permutation(begin(a), end(a)) sẽ tạo ra tập hợp có \dfrac{n!}{2!3!} phần tử.
• Nếu a có n phần tử nhưng chỉ có 2 loại phần tử: k số 0 và n-k số 1, thì next_permutation(begin(a), end(a)) sẽ tạo ra tập hợp gồm \dfrac{n!}{k! (n-k)!} phần tử, đây chính là tổ hợp n chập k của a.

---

Code để sinh tổ hợp n chập k khá đơn giản :V :V

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

int main() {
    int n = 5;
    int k = 3;
    std::vector<bool> a(n);               // mảng chỉ có 2 loại phần tử là 0 và 1
    std::fill(begin(a), begin(a) + k, 0); // k phần tử đầu tiên là 0
    std::fill(begin(a) + k, end(a), 1);   // n-k phần tử còn lại là 1
    do {
        for (int i = 0; i < n; ++i)
            if (a[i] == 0) // vì ta cần n chập k nên tìm a[i] == 0 vì ở đây có k phần tử 0
                std::cout << i + 1 << " ";
        std::cout << "\n";
    } while (std::next_permutation(begin(a), end(a)));
}

in ra

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

---

đã có thể in ra tổ hợp n chập k theo thứ tự thì từ đây có thể giải bài toán tìm tập con đứng trước của chủ thớt dễ dàng :V

[Sherly1001]

Rõ là bài này đâu phải làm như v đâu TT ca.

---

Trc tiên thì có cấu hình đầu tiên là [1, 2, 3, ..., k] và cấu hình cuối cùng là [n - k + 1, n - k + 2, n - k + 3, ..., n]

Giờ là phải sinh ra cấu hình liền trước từ cấu hình hiện tại. :V :V

Để ý vào dãy sau:

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

• Với cấu hình đầu tiền thì đưa về cấu hình cuối cùng.

• Với cấu hình bất kỳ thì ta tìm phần tử đầu tiên của cấp số cộng công sai 1 ở cuối dãy.
  VD: cấu hình [2, 4, 5] thì CSC công sai 1 ở cuối dãy là [4, 5] => phần tử cần tìm là 4. Hay cấu hình [2, 3, 4] => CSC là [2, 3, 4] => phần tử cần tìm là 2.

• Giảm phần tử đó đi một, và đưa các phần từ sau nó tương ứng với cấu hình cuối cùng.
  VD: [2, 3, 4] => tìm được phần tử 2 qua bước trên => giảm đi 1 còn [1, 3, 4]. Các phần tử sau nó đưa về tương ứng với cấu hình cuối. Cấu hình cuối của trường hợp này là [3, 4, 5] thì sẽ thành [1, 4, 5].

Code xấu nên phải dấu đi. :V :V

#include <iostream>
#include <vector>

std::vector<int> &pred(std::vector<int> &x, int n, int k) {
    int i = k - 1;
    while (i > 0 && x[i] == x[i - 1] + 1) --i;
    if (x[i] > 1) --x[i];
    else x[i] = n - k + 1;
    for (int j = i + 1; j < k; ++j) x[j] = n - k + j + 1;
    return x;
}

std::ostream &operator<<(std::ostream &os, const std::vector<int> &a) {
    for (auto &i: a) std::cout << i << ' ';
    return os;
}

int main() {
    std::vector<int> a = {2, 3, 5};

    for (int i = 0; i < 10; ++i) {
        std::cout << pred(a, 5, 3) << '\n';
    }
}

2 3 4
1 4 5
1 3 5
1 3 4
1 2 5
1 2 4
1 2 3
3 4 5
2 4 5
2 3 5