Bài toán: Viết chương trình liệt kê các hoán vị của {1,2,…,n}. Show
Giới thiệu bài toán liệt kê hoán vị tổ hợpHoá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ợpYê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:
Hướng dẫn giải bài toán liệt kê hoán vị tổ hợpSử dụng phương pháp quay lui để giải quyết bài toánChú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: Liệt kê hoán vịCode tham khảo
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 ! |