[Thuật toán] Liệt kê hoán vị

Ta sẽ lập chương trình liệt kê các hoán vị của {1, 2, …, n} theo thứ tự từ điển.
Ví dụ với n = 3, ta phải liệt kê đủ 6 hoán vị:

1   2   3
1   3   2
2   1   3
2   3   1
3   1   2
3   2   1

Như vậy 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à a = 〈3, 2, 6, 5, 4, 1〉, xét 4 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ị 4 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 a[2] = 2, thay nó bằng một giá trị khác. Ta sẽ thay bằng giá trị nào?, không thể là 1 bởi nếu vậy sẽ được hoán vị nhỏ hơn, không thể là 3 vì đã có a[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, 5, 6. Vì cần một hoán vị vừa đủ lớn hơn hiện tại nên ta chọn a[2] = 4. Còn các giá trị (a[3], a[4], a[5], a[6]) sẽ lấy trong tập {2, 6, 5, 1}. Cũng vì tính vừa  đủ lớn nên ta sẽ tìm biểu diễn nhỏ nhất của 4 số này gán cho a[3], a[4], a[5], a[6] tức là 〈1, 2, 5, 6〉. Vậy hoán vị mới sẽ là 〈3, 4, 1, 2, 5, 6〉.

Ta có nhận xét gì qua ví dụ này: Đoạn cuối của hoán vị hiện tại được xếp giảm dần, số a[5] = 4 là số nhỏ nhất trong đoạn cuối giảm dần thoả mãn điều kiện lớn hơn a[2] = 2. Nếu đổi chỗ a[5] cho a[2] thì ta sẽ được a[2] = 4 và đoạn cuối vẫn được sắp xếp giảm dần. Khi đó muốn biểu diễn nhỏ nhất cho các giá trị trong đoạn cuối thì ta chỉ cần đảo ngược đoạn cuối. Trong trường hợp hoán vị hiện tại là 〈2, 1, 3, 4〉 thì hoán vị kế tiếp sẽ là 〈2, 1, 4, 3〉. Ta cũng có thể coi hoán vị 〈2, 1, 3, 4〉 có đoạn cuối giảm dần, đoạn cuối này chỉ gồm 1 phần tử (4) Vậy kỹ thuật sinh hoán vị kế tiếp từ hoán vị hiện tại có thể xây dựng như sau:

1. Xác định đoạn cuối giảm dần dài nhất, tìm chỉ số i của phần tử a[i] bắt đầu đoạn cuối đó. Điều này đồng nghĩa với việc tìm từ vị trí cuối dãy lên đến phần tử thứ 2 (vì nếu tìm được ở phần tử đầu tiên tức đó là hoán vị cuối cùng rồi nên không cần), gặp chỉ số i đầu tiên thỏa mãn a[i-1] < a[i].
2. Nếu tìm thấy chỉ số i như trên
   – Trong đoạn cuối giảm dần, tìm phần tử a[k] nhỏ nhất thoả mãn điều kiện a[k] > a[i-1]. Do đoạn cuối giảm dần, điều này thực hiện bằng cách tìm từ cuối dãy lên đầu gặp chỉ số k đầu tiên thoả mãn a[k] > a[i-1] (có thể dùng tìm kiếm nhị phân).
   – Đảo giá trị a[k] và a[i-1]
   – Lật ngược thứ tự đoạn cuối giảm dần (từ a[i] đến a[k]) trở thành tăng dần.
3. Nếu không tìm thấy tức là toàn dãy đã sắp giảm dần, đây là cấu hình cuối cùng.

code minh họa C++.

/*
code by nguyenvanquan7826
*/

#include <cstdio> 
#include <cstdlib>
#include <iostream>
#include <algorithm>		// thu vien chua ham swap (hoan vi 2 so)
using namespace std;

int main(int argc, char **argv)
{
	int n, *a;
	scanf("%d", &n);
	a = new int[n];
	for (int i=0; i<n; i++)			// khoi tao va in ra cau hinh ban dau
	{
		a[i] = i+1;
		printf("%d   ", a[i]);
	}	
	printf("n");
	
	int i = n-1;		// i la vi tri ma doan cuoi giam dan
	while (i>0)			// trong khi doan cuoi khong phai bat dau tu vi tri dau tien
	{
		i = n-1;
		while (a[i] < a[i-1])	// tim vi tri dau tien ma doan cuoi giam dan
		{
			i--; 
		}
		
		if (i>0)		// Neu tim duoc i
		{
			int k;		// tim so a[k] nho nhat trong doan giam dan ma a[k] > a[i-1]
			for (k = n-1; k >= i; k--)		
			{
				if (a[k] > a[i-1])		
				{
					break;
				}
				
			}
			swap(a[k], a[i-1]);		// hoan vi a[k] va a[i-1]
			
			// dao nguoc doan cuoi giam dan thanh tang dan
			for (int k = i; k < i + (n - i) / 2; k++)	
			{
				swap(a[k], a[n - 1 - k + i]);
			}
			
			for (int k = 0; k < n; k++)		// in hoan vi ra
			{
				printf("%d   ", a[k]);
			}
			printf("n");
		}
	}
	
	return 0; 
}

Bài viết trích dẫn từ Giáo trình cấu trúc dữ liệu và giải thuật của thầy Lê Minh Hoàng. Các bạn có thể xem code Pascal như trong giáo trình thầy đã viết.