Thuật toán sinh trong C++ và bài tập luyện tập (Full Code)

#include <iostream>
using namespace std;
int n, a[100], ok;
void ktao() {
    for (int i = 1; i <= n; i++) {
        a[i] = 0;
    }
}
void sinh() {
    // Bat dau tu bit cuoi cung, di tim bit 0 dau tien
    int i = n;
    while (i > 0 && a[i] == 1) {
        a[i] = 0;
        --i;
    }
    if (i == 0) {
       ok = 0; // day la cau hinh cuoi cung
    }
    else {
       a[i] = 1;
    }
}
int main() {
    cin >> n;
    ok = 1;
    ktao();
    while(ok) {
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
        sinh();
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int n, ok;
vector<int> a;

void ktao() {
    a.assign(n, 0); // Khởi tạo vector với n phần tử đều bằng 0
}

void sinh() {
    // Bắt đầu từ bit cuối cùng, đi tìm bit 0 đầu tiên
    int i = n - 1;
    while (i >= 0 && a[i] == 1) {
        a[i] = 0;
        --i;
    }
    if (i < 0) {
        ok = 0; // Đây là cấu hình cuối cùng
    } else {
        a[i] = 1;
    }
}

int main() {
    cin >> n;
    ok = 1;
    ktao();
    while (ok) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
        sinh();
    }
    return 0;
}

#include <iostream>
using namespace std;

int n, k, a[100], ok;
void ktao() {
    for (int i = 1; i <= k; i++)
        a[i] = i;
}
void sinh() {
    int i = k;
    while (i >= 1 && a[i] == n-k+i) --i;
    if(i == 0) ok = 0;
    else {
        a[i]++;
        for (int j = i + 1; j <= k; j++)
            a[j] = a[j-1] + 1;
    }
}
int main() {
    cin >> n >> k;
    ok = 1;
    ktao();
    while(ok) {
        for (int i = 1; i <= k; i++)
            cout << a[i];
        cout << endl;
        sinh();
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int n, k, ok;
vector<int> a;

void ktao() {
    a.resize(k); // Khởi tạo vector với k phần tử
    for (int i = 0; i < k; i++)
        a[i] = i + 1;
}

void sinh() {
    int i = k - 1;
    while (i >= 0 && a[i] == n - k + i + 1) --i;
    if (i < 0) ok = 0;
    else {
        a[i]++;
        for (int j = i + 1; j < k; j++)
            a[j] = a[j - 1] + 1;
    }
}

int main() {
    cin >> n >> k;
    ok = 1;
    ktao();
    while (ok) {
        for (int i = 0; i < k; i++)
            cout << a[i];
        cout << endl;
        sinh();
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
int n, k, a[100], ok;
void ktao() {
    for(int i = 1; i <= n; i++)
        a[i] = i;
}
void sinh() {
    int i = n - 1;
    while(i >= 1 && a[i] > a[i+1]) --i;
    if(i == 0) ok = 0;
    else {
        // Di tim a[i] trong doan [i + 1, n]
        int j = n;
        while(a[i] > a[j]) --j;
        swap(a[i],a[j]); // Đổi chỗ
        reverse(a + i + 1, a + n + 1); // Lật ngược
    }
}
int main() {
    cin >> n;
    ok = 1;
    ktao();
    while(ok) {
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
        sinh();
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, ok;
vector<int> a;

void ktao() {
    a.resize(n); // Khởi tạo vector với n phần tử
    for (int i = 0; i < n; i++)
        a[i] = i + 1;
}

void sinh() {
    int i = n - 2;
    while (i >= 0 && a[i] > a[i + 1]) --i;
    if (i < 0) ok = 0;
    else {
        // Đi tìm a[i] trong đoạn [i + 1, n]
        int j = n - 1;
        while (a[i] > a[j]) --j;
        swap(a[i], a[j]); // Đổi chỗ dùng hàm có sẵn
        reverse(a.begin() + i + 1, a.end()); // Lật ngược
    }
}

int main() {
    cin >> n;
    ok = 1;
    ktao();
    while (ok) {
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
        sinh();
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Sắp xếp mảng ban đầu theo thứ tự tăng dần
    sort(arr, arr + n);

    do {
        // In hoán vị hiện tại
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    } while (next_permutation(arr, arr + n));// Dùng hàm có sẵn

    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {1, 2, 3};
    int n = arr.size();

    // Sắp xếp vector ban đầu theo thứ tự tăng dần
    sort(arr.begin(), arr.end());

    do {
        // In hoán vị hiện tại
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    } while (next_permutation(arr.begin(), arr.end()));

    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
// Sinh phân hoạch nguyên của số tự nhiên n
// Phân tích n thành tổng các số tự nhiên bằng n
int n, a[100], ok, cnt;
void ktao() {
    cnt = 1; a[1] = n;
}
void sinh() {
    int i = cnt; // Bắt đầu bằng phần tử đầu tiên từ phải sang
    while(i >= 1 & a[i] == 1) i--; // Dịch sang trái đến khi gặp phần tử khác 1
    if(i == 0) ok = 0; // Nếu chạy đến phần tử đầu tiên, hoàn thành
    else {
        a[i]--; // Gặp phần tử > 1 giảm đi 1
        int d = cnt - i + 1; // Tìm xem có bao nhiêu phần tử 1 sau a[i] (số lượng số 1 đã bỏ qua ở vòng lặp while)
        // Cộng thêm 1 do giảm a[i] đi 1 đơn vị
        cnt = i; // Đặt lại chỉ số cnt = i
        int q = d / a[i];
        int r = d % a[i];
        if(q)
            for(int j = 1; j <= q; j++) {
                cnt++;
                a[cnt] = a[i]; // Viết thêm q lần a[i]
            }
            if (r) {
                cnt++;
                a[cnt] = r; // Viết thêm số dư
            }
    }
}

int main() {
    cin >> n;
    ktao();
    ok = 1;
    while(ok) {
        for(int i = 1; i <= cnt; i++)
            cout << a[i] << " ";
        cout << endl;
        sinh();
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, ok, cnt;
vector<int> a;

void ktao() {
    cnt = 1;
    a.resize(1);
    a[0] = n;
}

void sinh() {
    int i = cnt - 1; // Bắt đầu bằng phần tử đầu tiên từ phải sang
    while (i >= 0 && a[i] == 1) i--; // Dịch sang trái đến khi gặp phần tử khác 1
    if (i < 0) ok = 0; // Nếu chạy đến phần tử đầu tiên, hoàn thành
    else {
        a[i]--; // Gặp phần tử > 1 giảm đi 1
        int d = cnt - i; // Tìm xem có bao nhiêu phần tử 1 sau a[i] (số lượng số 1 đã bỏ qua ở vòng lặp while)
        cnt = i + 1; // Đặt lại chỉ số cnt
        int q = d / a[i];
        int r = d % a[i];
        a.resize(cnt + q + (r > 0 ? 1 : 0)); // Điều chỉnh kích thước vector
        for (int j = 0; j < q; j++) {
            a[cnt++] = a[i]; // Viết thêm q lần a[i]
        }
        if (r) {
            a[cnt++] = r; // Viết thêm số dư
        }
    }
}

int main() {
    cin >> n;
    ktao();
    ok = 1;
    while (ok) {
        for (int i = 0; i < cnt; i++)
            cout << a[i] << " ";
        cout << endl;
        sinh();
    }
    return 0;
}

#include <iostream>
using namespace std;
int n, k, a[100], ok;

void sinh() {
    int i = n;
    while (i > 0 && a[i] == 1) {
        a[i] = 0;
        i--;
    }
    if(i == 0)
        ok = 0;
    else a[i] = 1;
}
bool check() {
    int res = 0;
    for(int i = 1; i <= n; i++) {
        res += a[i];
    }
    return res == k;
}
int main() {
    cin >> n >> k;
    ok = 1;
    while(ok) {
        if(check()) {
            for (int i = 1; i <= n; i++)
                cout << a[i] << " ";
            cout << endl;
        }
        sinh();
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int n, k, ok;
vector<int> a;

void sinh() {
    int i = n - 1;
    while (i >= 0 && a[i] == 1) {
        a[i] = 0;
        i--;
    }
    if (i < 0)
        ok = 0;
    else
        a[i] = 1;
}

bool check() {
    int res = 0;
    for (int i = 0; i < n; i++) {
        res += a[i];
    }
    return res == k;
}

int main() {
    cin >> n >> k;
    a.resize(n, 0); // Khởi tạo vector với n phần tử đều bằng 0
    ok = 1;
    while (ok) {
        if (check()) {
            for (int i = 0; i < n; i++)
                cout << a[i] << " ";
            cout << endl;
        }
        sinh();
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
void generateSubsets(const vector<int>& set) {
    int n = set.size();
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) cout << set[j] << " ";
        }
        cout << endl;
    }
}
int main() {
    vector<int> set = {1, 2, 3};
    generateSubsets(set);
    return 0;
}

#include <iostream>
using namespace std;

void generateSubsets(const int set[], int n) {
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) cout << set[j] << " ";
        }
        cout << endl;
    }
}

int main() {
    int set[] = {1, 2, 3}; // Mảng tĩnh
    int n = sizeof(set) / sizeof(set[0]); // Kích thước của mảng
    generateSubsets(set, n);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

void generatePermutations(string str) {
    sort(str.begin(), str.end());
    do {
        cout << str << endl;
    } while (next_permutation(str.begin(), str.end()));
}

int main() {
    string str;
    cout << "Nhập chuỗi ký tự: ";
    cin >> str;
    generatePermutations(str);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void generateIncreasingSequences(int n) {
    vector<int> sequence;
    int sum = 0;
    for (int i = 1; sum + i <= n; ++i) {
        sequence.push_back(i);
        sum += i;
    }
    while (!sequence.empty()) {
        for (int num : sequence) cout << num << " ";
        cout << endl;
        int rem_val = 0;
        while (!sequence.empty() && sequence.back() == 1) {
            rem_val += sequence.back();
            sequence.pop_back();
        }
        if (!sequence.empty()) {
            sequence.back()--;
            rem_val++;
            while (rem_val > sequence.back()) {
                sequence.push_back(sequence.back());
                rem_val -= sequence.back();
            }
            sequence.push_back(rem_val);
        }
    }
}

int main() {
    int n;
    cin >> n;
    generateIncreasingSequences(n);
    return 0;

#include <iostream>
using namespace std;

void generateIncreasingSequences(int n) {
    int sequence[100]; 
    int length = 0;    // Độ dài hiện tại của dãy
    int sum = 0;

    // Khởi tạo dãy tăng dần đầu tiên
    for (int i = 1; sum + i <= n; ++i) {
        sequence[length++] = i;
        sum += i;
    }

    while (length > 0) {
        // In dãy hiện tại
        for (int i = 0; i < length; ++i) {
            cout << sequence[i] << " ";
        }
        cout << endl;

        // Tìm phần tử cuối lớn hơn 1 để giảm giá trị
        int rem_val = 0; // Lưu giá trị dư
        while (length > 0 && sequence[length - 1] == 1) {
            rem_val += sequence[--length];
        }

        // Nếu dãy đã rỗng, thoát vòng lặp
        if (length == 0) break;

        // Giảm giá trị của phần tử cuối và cập nhật dãy
        sequence[length - 1]--;
        rem_val++;

        // Chia lại giá trị dư vào dãy
        while (rem_val > sequence[length - 1]) {
            sequence[length] = sequence[length - 1];
            rem_val -= sequence[length++];
        }
        sequence[length++] = rem_val;
    }
}

int main() {
    int n;
    cin >> n;
    generateIncreasingSequences(n);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void generateNonDecreasingSequences(int n) {
    vector<int> sequence(n, 1);
    while (true) {
        for (int num : sequence) cout << num << " ";
        cout << endl;

        int i = n - 1;
        while (i >= 0 && sequence[i] == n) --i;
        if (i < 0) break;

        ++sequence[i];
        for (int j = i + 1; j < n; ++j) sequence[j] = sequence[i];
    }
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;
    generateNonDecreasingSequences(n);
    return 0;
}

#include <iostream>
using namespace std;

void generateNonDecreasingSequences(int n) {
    int sequence[100];  
    fill(sequence, sequence + n, 1);  // Khởi tạo tất cả phần tử trong mảng bằng 1
    
    while (true) {
        for (int i = 0; i < n; ++i) cout << sequence[i] << " ";
        cout << endl;

        int i = n - 1;
        while (i >= 0 && sequence[i] == n) --i;
        if (i < 0) break;

        ++sequence[i];
        for (int j = i + 1; j < n; ++j) sequence[j] = sequence[i];
    }
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;
    generateNonDecreasingSequences(n);
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
vector<int> a;
bool ok;

// Khởi tạo mảng toàn 0
void ktao() {
    a.assign(n, 0);
    ok = true;
}

// Sinh cấu hình tiếp theo
void sinh() {
    int i = n - 1;
    while (i >= 0 && a[i] == 1) {
        a[i] = 0;
        --i;
    }
    if (i < 0) ok = false; // Cấu hình cuối cùng
    else a[i] = 1;
}

// In dãy nhị phân
void in() {
    for (int x : a) cout << x << " ";
    cout << endl;
}

// Kiểm tra số bit 1 trong dãy
bool checkBit1(int k) {
    return count(a.begin(), a.end(), 1) == k;
}

// Kiểm tra tính đối xứng
bool checkDoiXung() {
    for (int i = 0; i < n / 2; ++i) {
        if (a[i] != a[n - 1 - i]) return false;
    }
    return true;
}

// Kiểm tra không có hai số 1 liên tiếp
bool checkKhongHaiSo1LienTiep() {
    for (int i = 0; i < n - 1; ++i) {
        if (a[i] == 1 && a[i + 1] == 1) return false;
    }
    return true;
}

// Kiểm tra tổng các phần tử ở vị trí lẻ là lẻ
bool checkTongLe() {
    int sum = 0;
    for (int i = 0; i < n; i += 2) {
        sum += a[i];
    }
    return sum % 2 == 1;
}

// Kiểm tra vị trí chẵn chỉ chứa 0
bool checkViTriChan() {
    for (int i = 1; i < n; i += 2) {
        if (a[i] != 0) return false;
    }
    return true;
}

// Kiểm tra không chứa chuỗi con "111"
bool checkKhongChuoi111() {
    for (int i = 0; i < n - 2; ++i) {
        if (a[i] == 1 && a[i + 1] == 1 && a[i + 2] == 1) return false;
    }
    return true;
}

int main() {
    cin >> n;

    // Bài 1: Sinh tất cả dãy nhị phân
    cout << "\nBai 1: Tat ca cac day nhi phan" << endl;
    ktao();
    while (ok) {
        in();
        sinh();
    }

    // Bài 2: Sinh dãy nhị phân theo thứ tự ngược
    cout << "\nBai 2: Day nhi phan theo thu tu nguoc" << endl;
    ktao();
    do {
        in();
    } while (prev_permutation(a.begin(), a.end()));

    // Bài 3: Đếm dãy có k bit 1
    cout << "\nBai 3: Day nhi phan co dung k bit 1" << endl;
    cin >> k;
    ktao();
    while (ok) {
        if (checkBit1(k)) in();
        sinh();
    }

    // Bài 4: Sinh dãy không có hai số 1 liên tiếp
    cout << "\nBai 4: Day khong co hai so 1 lien tiep" << endl;
    ktao();
    while (ok) {
        if (checkKhongHaiSo1LienTiep()) in();
        sinh();
    }

    // Bài 5: Sinh dãy có đúng k bit 1
    cout << "\nBai 5: Day co dung k bit 1" << endl;
    cin >> k;
    ktao();
    while (ok) {
        if (checkBit1(k)) in();
        sinh();
    }

    // Bài 6: Sinh dãy đối xứng
    cout << "\nBai 6: Day doi xung" << endl;
    ktao();
    while (ok) {
        if (checkDoiXung()) in();
        sinh();
    }

    // Bài 7: Sinh theo thứ tự từ điển
    cout << "\nBai 7: Day theo thu tu tu dien" << endl;
    ktao();
    while (ok) {
        in();
        sinh();
    }

    // Bài 8: Tổng các phần tử ở vị trí lẻ là lẻ
    cout << "\nBai 8: Tong phan tu vi tri le la le" << endl;
    ktao();
    while (ok) {
        if (checkTongLe()) in();
        sinh();
    }

    // Bài 9: Vị trí chẵn chỉ chứa số 0
    cout << "\nBai 9: Vi tri chan chi chua so 0" << endl;
    ktao();
    while (ok) {
        if (checkViTriChan()) in();
        sinh();
    }

    // Bài 10: Không chứa chuỗi con "111"
    cout << "\nBai 10: Day khong chua chuoi con 111" << endl;
    ktao();
    while (ok) {
        if (checkKhongChuoi111()) in();
        sinh();
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
vector<int> a;
bool ok;

// Khởi tạo cấu hình đầu tiên
void ktao() {
    a.resize(k);
    for (int i = 0; i < k; i++) a[i] = i + 1;
    ok = true;
}

// Sinh cấu hình tiếp theo
void sinh() {
    int i = k - 1;
    while (i >= 0 && a[i] == n - k + i + 1) i--;
    if (i < 0) ok = false;
    else {
        a[i]++;
        for (int j = i + 1; j < k; j++) a[j] = a[j - 1] + 1;
    }
}

// In tổ hợp hiện tại
void in() {
    for (int x : a) cout << x << " ";
    cout << endl;
}

// Kiểm tra tổng giá trị lẻ
bool checkTongLe() {
    int sum = 0;
    for (int x : a) sum += x;
    return sum % 2 == 1;
}

// Kiểm tra không chứa phần tử đầu tiên
bool checkKhongChua1() {
    return find(a.begin(), a.end(), 1) == a.end();
}

// Kiểm tra chỉ chứa số lẻ
bool checkChiSoLe() {
    for (int x : a) if (x % 2 == 0) return false;
    return true;
}

// Kiểm tra có phần tử liên tiếp
bool checkLienTiep() {
    for (int i = 1; i < k; i++) {
        if (a[i] == a[i - 1] + 1) return true;
    }
    return false;
}

// Kiểm tra tổng lớn hơn S
bool checkTongLonHonS(int S) {
    int sum = 0;
    for (int x : a) sum += x;
    return sum > S;
}

// Kiểm tra không chứa số chẵn
bool checkKhongSoChan() {
    for (int x : a) if (x % 2 == 0) return false;
    return true;
}

// Kiểm tra chỉ chứa số nguyên tố
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}

bool checkChiSoNguyenTo() {
    for (int x : a) if (!isPrime(x)) return false;
    return true;
}

// Tìm độ chênh lệch nhỏ nhất
int doChenhLech() {
    return a[k - 1] - a[0];
}

int main() {
    cin >> n >> k;

    // Bài 1: Sinh tất cả tổ hợp chập k của n
    cout << "\nBai 1: Tat ca to hop chap k cua n" << endl;
    ktao();
    while (ok) {
        in();
        sinh();
    }

    // Bài 2: Sinh tổ hợp chập k theo thứ tự ngược
    cout << "\nBai 2: To hop chap k theo thu tu nguoc" << endl;
    ktao();
    vector<vector<int>> toHop;
    while (ok) {
        toHop.push_back(a);
        sinh();
    }
    reverse(toHop.begin(), toHop.end());
    for (auto v : toHop) {
        for (int x : v) cout << x << " ";
        cout << endl;
    }

    // Bài 3: Tổng giá trị chỉ số lẻ
    cout << "\nBai 3: To hop co tong gia tri le" << endl;
    ktao();
    while (ok) {
        if (checkTongLe()) in();
        sinh();
    }

    // Bài 4: Không chứa phần tử đầu tiên
    cout << "\nBai 4: To hop khong chua phan tu dau tien" << endl;
    ktao();
    while (ok) {
        if (checkKhongChua1()) in();
        sinh();
    }

    // Bài 5: Chỉ chứa số lẻ
    cout << "\nBai 5: To hop chi chua so le" << endl;
    ktao();
    while (ok) {
        if (checkChiSoLe()) in();
        sinh();
    }

    // Bài 6: Có phần tử liên tiếp
    cout << "\nBai 6: To hop co phan tu lien tiep" << endl;
    ktao();
    while (ok) {
        if (checkLienTiep()) in();
        sinh();
    }

    // Bài 7: Tổng lớn hơn S
    int S;
    cout << "Nhap S: ";
    cin >> S;
    cout << "\nBai 7: To hop co tong lon hon S" << endl;
    ktao();
    while (ok) {
        if (checkTongLonHonS(S)) in();
        sinh();
    }

    // Bài 8: Không chứa số chẵn
    cout << "\nBai 8: To hop khong chua so chan" << endl;
    ktao();
    while (ok) {
        if (checkKhongSoChan()) in();
        sinh();
    }

    // Bài 9: Chỉ chứa số nguyên tố
    cout << "\nBai 9: To hop chi chua so nguyen to" << endl;
    ktao();
    while (ok) {
        if (checkChiSoNguyenTo()) in();
        sinh();
    }

    // Bài 10: Độ chênh lệch nhỏ nhất
    cout << "\nBai 10: To hop co do chenh lech nho nhat" << endl;
    ktao();
    vector<vector<int>> minChenhLech;
    int minDiff = INT_MAX;
    while (ok) {
        int diff = doChenhLech();
        if (diff < minDiff) {
            minChenhLech.clear();
            minDiff = diff;
        }
        if (diff == minDiff) minChenhLech.push_back(a);
        sinh();
    }
    for (auto v : minChenhLech) {
        for (int x : v) cout << x << " ";
        cout << endl;
    }

    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int n;
vector<int> a;
bool ok;

// Khởi tạo cấu hình đầu tiên
void ktao() {
    a.resize(n);
    for (int i = 0; i < n; i++) a[i] = i + 1;
    ok = true;
}

// Sinh cấu hình tiếp theo
void sinh() {
    int i = n - 2;
    while (i >= 0 && a[i] > a[i + 1]) i--;
    if (i < 0) ok = false;
    else {
        int j = n - 1;
        while (a[i] > a[j]) j--;
        swap(a[i], a[j]);
        reverse(a.begin() + i + 1, a.end());
    }
}

// In hoán vị hiện tại
void in() {
    for (int x : a) cout << x << " ";
    cout << endl;
}

// Kiểm tra chỉ chứa số lẻ
bool checkChiSoLe() {
    for (int x : a) if (x % 2 == 0) return false;
    return true;
}

// Kiểm tra không chứa số nguyên tố
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}

bool checkKhongSoNguyenTo() {
    for (int x : a) if (isPrime(x)) return false;
    return true;
}

// Kiểm tra tổng phần tử chẵn
bool checkTongChan() {
    int sum = 0;
    for (int x : a) sum += x;
    return sum % 2 == 0;
}

// Kiểm tra độ chênh lệch nhỏ nhất giữa hai phần tử liên tiếp
bool checkChenhLechNhoNhat() {
    int minDiff = INT_MAX;
    for (int i = 1; i < n; i++) {
        minDiff = min(minDiff, abs(a[i] - a[i - 1]));
    }
    return minDiff == 1;
}

// Kiểm tra không chứa cặp liên tiếp chênh lệch > 2
bool checkKhongChenhLechLonHon2() {
    for (int i = 1; i < n; i++) {
        if (abs(a[i] - a[i - 1]) > 2) return false;
    }
    return true;
}

// Kiểm tra đối xứng
bool checkDoiXung() {
    for (int i = 0; i < n / 2; i++) {
        if (a[i] != a[n - 1 - i]) return false;
    }
    return true;
}

// Kiểm tra không có số lẻ ở vị trí chẵn
bool checkKhongLeViTriChan() {
    for (int i = 1; i < n; i += 2) {
        if (a[i] % 2 == 1) return false;
    }
    return true;
}

// Kiểm tra số lớn nhất ở giữa
bool checkMaxGiua() {
    int maxVal = *max_element(a.begin(), a.end());
    if (n % 2 == 1) return a[n / 2] == maxVal;
    return a[n / 2] == maxVal || a[n / 2 - 1] == maxVal;
}

int main() {
    cin >> n;

    // Bài 1: Sinh tất cả hoán vị
    cout << "\nBai 1: Tat ca hoan vi" << endl;
    ktao();
    while (ok) {
        in();
        sinh();
    }

    // Bài 2: Sinh hoán vị theo thứ tự ngược
    cout << "\nBai 2: Hoan vi theo thu tu nguoc" << endl;
    ktao();
    vector<vector<int>> hoanVi;
    while (ok) {
        hoanVi.push_back(a);
        sinh();
    }
    reverse(hoanVi.begin(), hoanVi.end());
    for (auto v : hoanVi) {
        for (int x : v) cout << x << " ";
        cout << endl;
    }

    // Bài 3: Chỉ chứa số lẻ
    cout << "\nBai 3: Hoan vi chi chua so le" << endl;
    ktao();
    while (ok) {
        if (checkChiSoLe()) in();
        sinh();
    }

    // Bài 4: Không chứa số nguyên tố
    cout << "\nBai 4: Hoan vi khong chua so nguyen to" << endl;
    ktao();
    while (ok) {
        if (checkKhongSoNguyenTo()) in();
        sinh();
    }

    // Bài 5: Tổng là số chẵn
    cout << "\nBai 5: Hoan vi co tong chan" << endl;
    ktao();
    while (ok) {
        if (checkTongChan()) in();
        sinh();
    }

    // Bài 6: Có độ chênh lệch nhỏ nhất
    cout << "\nBai 6: Hoan vi co chen lech nho nhat" << endl;
    ktao();
    while (ok) {
        if (checkChenhLechNhoNhat()) in();
        sinh();
    }

    // Bài 7: Không có cặp liên tiếp chênh lệch > 2
    cout << "\nBai 7: Hoan vi khong co chen lech lon hon 2" << endl;
    ktao();
    while (ok) {
        if (checkKhongChenhLechLonHon2()) in();
        sinh();
    }

    // Bài 8: Hoán vị đối xứng
    cout << "\nBai 8: Hoan vi doi xung" << endl;
    ktao();
    while (ok) {
        if (checkDoiXung()) in();
        sinh();
    }

    // Bài 9: Không có số lẻ ở vị trí chẵn
    cout << "\nBai 9: Hoan vi khong co so le o vi tri chan" << endl;
    ktao();
    while (ok) {
        if (checkKhongLeViTriChan()) in();
        sinh();
    }

    // Bài 10: Số lớn nhất ở giữa
    cout << "\nBai 10: Hoan vi co so lon nhat o giua" << endl;
    ktao();
    while (ok) {
        if (checkMaxGiua()) in();
        sinh();
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, a[100], ok, cnt;

void ktao() {
    cnt = 1; 
    a[1] = n;
    ok = 1;
}

void sinh() {
    int i = cnt; // Bắt đầu từ phần tử cuối cùng
    while (i >= 1 && a[i] == 1) i--;
    if (i == 0) ok = 0;
    else {
        a[i]--;
        int d = cnt - i + 1;
        cnt = i;
        int q = d / a[i];
        int r = d % a[i];
        for (int j = 1; j <= q; j++) a[++cnt] = a[i];
        if (r) a[++cnt] = r;
    }
}

void in() {
    for (int i = 1; i <= cnt; i++) cout << a[i] << " ";
    cout << endl;
}

bool checkChiSoLe() {
    for (int i = 1; i <= cnt; i++) if (a[i] % 2 == 0) return false;
    return true;
}

bool checkChiSoChan() {
    for (int i = 1; i <= cnt; i++) if (a[i] % 2 != 0) return false;
    return true;
}

bool checkSoPhanTuBangK(int k) {
    return cnt == k;
}

bool checkKhongTrungLap() {
    for (int i = 1; i < cnt; i++) {
        for (int j = i + 1; j <= cnt; j++) {
            if (a[i] == a[j]) return false;
        }
    }
    return true;
}

bool checkBoiSoCuaM(int m) {
    for (int i = 1; i <= cnt; i++) if (a[i] % m != 0) return false;
    return true;
}

bool checkTangDan() {
    for (int i = 1; i < cnt; i++) if (a[i] > a[i + 1]) return false;
    return true;
}

bool checkGiamDan() {
    for (int i = 1; i < cnt; i++) if (a[i] < a[i + 1]) return false;
    return true;
}

bool checkMaxNhoHonBangX(int x) {
    for (int i = 1; i <= cnt; i++) if (a[i] > x) return false;
    return true;
}

bool checkTongLe() {
    int sum = 0;
    for (int i = 1; i <= cnt; i++) sum += a[i];
    return sum % 2 != 0;
}

int main() {
    cin >> n;

    // Bài 1: Sinh tất cả phân hoạch
    cout << "\nBai 1: Tat ca phan hoach" << endl;
    ktao();
    while (ok) {
        in();
        sinh();
    }

    // Bài 2: Phân hoạch chỉ chứa các số lẻ
    cout << "\nBai 2: Phan hoach chi chua so le" << endl;
    ktao();
    while (ok) {
        if (checkChiSoLe()) in();
        sinh();
    }

    // Bài 3: Phân hoạch chỉ chứa các số chẵn
    cout << "\nBai 3: Phan hoach chi chua so chan" << endl;
    ktao();
    while (ok) {
        if (checkChiSoChan()) in();
        sinh();
    }

    // Bài 4: Phân hoạch có số phần tử bằng k
    int k;
    cout << "\nNhap k: ";
    cin >> k;
    cout << "\nBai 4: Phan hoach co so phan tu bang k" << endl;
    ktao();
    while (ok) {
        if (checkSoPhanTuBangK(k)) in();
        sinh();
    }

    // Bài 5: Phân hoạch không có số trùng lặp
    cout << "\nBai 5: Phan hoach khong co so trung lap" << endl;
    ktao();
    while (ok) {
        if (checkKhongTrungLap()) in();
        sinh();
    }

    // Bài 6: Phân hoạch có các phần tử là bội số của m
    int m;
    cout << "\nNhap m: ";
    cin >> m;
    cout << "\nBai 6: Phan hoach co cac phan tu la boi so cua m" << endl;
    ktao();
    while (ok) {
        if (checkBoiSoCuaM(m)) in();
        sinh();
    }

    // Bài 7: Phân hoạch tăng dần
    cout << "\nBai 7: Phan hoach tang dan" << endl;
    ktao();
    while (ok) {
        if (checkTangDan()) in();
        sinh();
    }

    // Bài 8: Phân hoạch giảm dần
    cout << "\nBai 8: Phan hoach giam dan" << endl;
    ktao();
    while (ok) {
        if (checkGiamDan()) in();
        sinh();
    }

    // Bài 9: Phân hoạch có phần tử lớn nhất <= x
    int x;
    cout << "\nNhap x: ";
    cin >> x;
    cout << "\nBai 9: Phan hoach co phan tu lon nhat <= x" << endl;
    ktao();
    while (ok) {
        if (checkMaxNhoHonBangX(x)) in();
        sinh();
    }

    // Bài 10: Phân hoạch có tổng là số lẻ
    cout << "\nBai 10: Phan hoach co tong le" << endl;
    ktao();
    while (ok) {
        if (checkTongLe()) in();
        sinh();
    }

    return 0;
}