Liệt kê các hoán vị tổ hợp sử dụng code c++

Bài toán: Viết chương trình liệt kê các hoán vị của {1,2,…,n}.

• Input

• 3

   

• Ouput

• 1 2 3
  1 3 2
  2 1 3
  2 3 1
  3 1 2
  3 2 1

Giới thiệu bài toán liệt kê hoán vị tổ hợp

Hoán vị tổ hợp là gì ?

Hoán vị là một dãy theo thứ tự chứa mỗi phần tử của một tập hợp một và các phần tử đó chỉ xuất hiện một lần duy nhất.

Ví dụ: A {1, 2, 3} thì {1, 2, 3} hoặc {2, 1, 3} được gọi là một hoán vị không lặp của A.

Bài toán này chúng ta chỉ làm về hoán vị không lặp.

Bài toán liệt kê hoán vị tổ hợp

Yêu cầu của bài toán là chúng ta phải nhập một số nguyên dương n, sau đó chương trình phải liệt kê tất cả các hoán vị của 1,2,3…n

Giả sử với n = 3:

• Khi đó hoán vị đầu tiên sẽ là 1 2 3
• Hoán vị tiếp theo sẽ phải lớn hơn hoán vị ban đầu 1 3 2
• Tương tự như vậy hoán cuối cùng sẽ là hoán vị lớn nhất 3 2 1

Hướng dẫn giải bài toán liệt kê hoán vị tổ hợp

Sử dụng phương pháp quay lui để giải quyết bài toán

Chúng ta sẽ dùng một mảng A[n+1] lưu các hoán vị, khi đó các hoán vị sẽ được biểu diễn như sau:

A[1], A[2], A[3], …,A[n].

Trong đó A[i] ≠ A[j] Với mọi i,j ∈ [1,n] và i ≠ j.

Để xác nhận một phần tử chỉ được dùng một lần ta sẽ dùng mảng Bool để lưu đánh dấu. Nếu phần tử chưa sử dụng thì sẽ có giá trị là 0 ngược lại sẽ có giá trị là 1. Ban đầu ta khởi tạo tất cả các phần tử trong mảng đều có giá trị là 0.

Ý tưởng của phương pháp quay lui là chúng ta sẽ chọn ra một phần tử chưa sử dụng. Lưu phần tử đó vào một cấu hình tổ hợp, sau đó đánh dấu nó đã sử dụng. Ta sẽ lặp lại công việc như trên đến khi đủ cấu hình cho một tổ hợp thì sẽ xuất ra màn hình. Sau khi xuất ra ta lại quay trở lại bước trước đó để đánh dấu là nó chưa được chọn.

Ta có thể hình dung bài toán như hình vẽ sau: Với n=3 thì bài toán trở thành liệt kê các hoán vị của các phần tử 1, 2, 3. Các hoán vị được liệt kê theo thứ tự từ điển tăng dần như hình vẽ sau:

Code tham khảo

#include<iostream>
#define MAX 20
using namespace std;

int n;
int Bool[MAX] = { 0 };//Đánh dấu chưa có phần tử nào sử dụng hết
int A[MAX];//Lưu hoán vị vào mảng A

void xuat() {
	for (int i = 1; i <= n; i++)
		cout << A[i] << " ";
	cout << endl;
}

void Try(int k) {
	for (int i = 1; i <= n; i++) {
		//Kiểm tra nếu phần tử chưa được chọn thì sẽ đánh dấu
		if (!Bool[i]) {
			A[k] = i; // Lưu một phần tử vào hoán vị
			Bool[i] = 1;//Đánh dấu đã dùng
			if (k == n)//Kiểm tra nếu đã chứa một hoán vị thì xuất
				xuat();
			else
				Try(k + 1);
			Bool[i] = 0;
		}
	}
}

int main() {
	cout << "Mhap n: ";
	cin >> n;
	Try(1);
}

Mhap n: 3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Bài viết của mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !