Sinh_Hoan_Vi.cpp

// Sinh_Hoan_Vi.cpp
#include <bits/stdc++.h>

using namespace std;

//Dao gia tri hai phan tu
void swap(int & a, int & b) {
    int tg = a;
    a = b;
    b = tg;
}

//Hien thi mot cau hinh
void view_config(int x[], int n) {
    for (int i = 1; i <= n; i++)
        cout << x[i];
    cout << endl;
}

//Sinh cau hinh moi tu cau hinh dang co
void next_config(int x[], int n, int i) {
    //Tim x[k] be nhat trong doan cuoi lon hon x[i]
    int k = n;
    while (x[k] < x[i]) {
        k--;
    }
    //Dao gia tri x[i] va x[k]
    swap(x[i], x[k]);
    //Dao nguoc doan cuoi
    int j = n;
    i++;
    while (i < j) {
        swap(x[i], x[j]);
        i++;
        j--;
    }
}

//Liet ke cac cau hinh
void listing_configs(int n) {
    int i;
    //x[n + 1] = { 0 };
    int x[n + 1];
    for (i = 0; i <= n; i++) x[i] = 0;
    //Cau hinh dau tien {1 2 ... n}
    for (i = 1; i <= n; i++) {
        x[i] = i;
    }
    do {
        view_config(x, n); //In mot cau hinh
        //Tim phan tu lien truoc doan cuoi giam dan
        i = n - 1;
        while (i > 0 && x[i] > x[i + 1]) i--;
        if (i > 0) { //Chua phai cau hinh cuoi
            next_config(x, n, i);
        }
    } while (i > 0);
}

int main() {
	int n;
	cout << "Nhap n: ";
	cin >> n;
	listing_configs(n);
	return 0;
}