Liệt kê các hoán vị - Sử dụng phương pháp quay lui để liệt kê các hoán vị

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

Input
0

1

Bạn đang đọc: Liệt kê các hoán vị – Sử dụng phương pháp quay lui để liệt kê các hoán vị

2
3
Ouput
01234567 1 2 31 3 22 1 32 3 13 1 23 2 1

Tóm Tắt

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 thành phần của một tập hợp một và những thành phần đó chỉ Open 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 tất cả 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à tất cả chúng ta phải nhập 1 số ít nguyên dương n, sau đó chương trình phải liệt kê tổng thể những 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 những hoán vị, khi đó những hoán vị sẽ được màn 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 thành phần chỉ được dùng một lần ta sẽ dùng mảng Bool để lưu ghi lại. Nếu thành phần 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 toàn bộ những thành phần trong mảng đều có giá trị là 0 .
Ý tưởng của chiêu thức quay lui là tất cả chúng ta sẽ chọn ra một thành phần chưa sử dụng. Lưu phần tử đó vào một thông số kỹ thuật tổng hợp, sau đó ghi lại nó đã sử dụng. Ta sẽ lặp lại việc làm như trên đến khi đủ thông số kỹ thuật cho một tổng hợp thì sẽ xuất ra màn hình hiển thị. Sau khi xuất ra ta lại quay trở lại bước trước đó để ghi lại là nó chưa được chọn .
Ta hoàn toàn có thể tưởng tượng bài toán như hình vẽ sau : Với n = 3 thì bài toán trở thành liệt kê những hoán vị của những thành phần 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 :