Thuật toán sinh hoán vị trong C++

• • Cho số nguyên dương n. Nhiệm vụ của bạn hãy liệt kê tất cả các hoán vị của 1,2,…,n.
  • Ví dụ n=3 ta có kết quả: 123, 132, 213, 231, 312, 321.
  • Hoán vị là một dãy theo thứ tự chứa một phần tử của một tập hợp và các phần tử đó hoàn toàn khác nhau. Mỗi phần tử chỉ xuất hiện một lần duy nhất trong dãy.

Công thức toán học: n=n!

• • Thuật toán:
  • Hoán vị đầu tiên sẽ là (1, 2, .., n). Hoán vị cuối cùng là(n, n-1,..1).
  • Hoán vị sẽ sinh ra phải lớn hơn hoán vị hiện tại, hơn thế nữa phải là hoán vị vừa đủ lớn hơn hoán vị hiện tại theo nghĩa không thế có một hoán vị nào khác chen giữa chúng khi sắp thứ tự.
  • Giả sử hoán vị hiện tại là x =(3, 4, 2, 1), xét 3 phần tử cuối cùng, ta thấy chúng được xếp giảm dần, điều đó có nghĩa là cho dù ta có hoán vị 3 phần tử này thế nào? ta cũng được một hoán vị bé hơn hoán vị hiện tại.
  • Như vậy ta phải xét đến x[1] = 3, thay nó bằng một giá trị khác. Ta sẽ thay bằng giá trị nào? không thế là 1,2 bởi nếu vậy sẽ được hoán vị nhỏ hơn? không thế là 3 vì đã có x[1] = 3 rồi (phân tử sau không được chọn vào những giá trị mà phân tử trước đã chọn). Còn lại các giá trị 4. Vì cần một hoán vị vừa đủ lớn hơn hiện tại nên ta chọn x[1] = 4. Còn các giá trị (x[2], x[3], x[4]) sẽ lấy trong tập {2, 1, 3} và sắp xếp tăng dần. Vậy hoán vị mới sẽ là (4, 1, 2, 3).
  • Code C++:

 
#include <bits/stdc++.h>
using namespace std;
void Swap(int &x, int &y)
{
	int tg; //bien trung gian
	tg = x;
	x = y;
	y = tg;
}
void khoitaocauhinhbandau(int a[], int n)
{
	for (int i = 1; i <= n; i++)
		a[i] = i;
}
void incauhinh(int a[], int n)
{
	for (int i = 1; i <= n; i++)
	cout << a[i];
	cout <<endl;
}
void sapxeptang (int a[], int n, int vt)
{
	for (int i = vt; i < n; i++)
	{
		for (int j = i+1; j <= n; j++)
		{
			if (a[i] > a[j])
				Swap(a[i],a[j]);
		}
	}
}	
int main() 
{
	int a[100];
    int n;
    cout << "Nhap n: ";
    cin >> n;
    khoitaocauhinhbandau(a,n);
    incauhinh(a, n);
    while(true)
    {
    	int i;
    	for (i =n; i > 0; i--) //duyet tu cuoi len 1 2 3 4, 4321
    	{
    		if (i==1) // neu duyet het day giam het roi
    			return 0;//thi thoat ra vi no la cau hinh cuoi roi
    		if (a[i-1] < a[i])
    			break;
    	}
    	for (int j =n; j >= i; j--)
    	{
    		if (a[j] > a[i-1])
    		{
    			Swap(a[j],a[i-1]);//doi cho
    			sapxeptang (a, n, i);
    			incauhinh(a, n);
    			break;
    		}
    	}
    }
    
}

– Kết quả: