Một hoán vị có độ dài n là một tập hợp có thứ tự không lặp lại các số 1, 2, ..., n. Ví dụ: [3, 1, 2] và [5, 4, 3, 2, 1] là hoán vị, nhưng [1, 2, 1, 3] và [1, 2, 4] thì không.
Nếu nhiệm vụ được rút gọn thành thực tế là cần phải lặp lại tất cả các hoán vị có độ dài n, thì bạn có thể sử dụng một cơ chế thuận tiện trong C ++, được gọi là "next_permutation".
Bạn có thể đọc thêm về nó trong tài liệu, nhưng điểm mấu chốt là hàm này thay đổi mảng đã truyền đến hoán vị tiếp theo theo thứ tự từ điển (thường rõ ràng và tên của nó).
Để sử dụng next_permutation, bạn cần đưa vào thư viện thuật toán (nghĩa là viết #include <algorithm> ở đầu chương trình)
Ví dụ:
véc tơ mảng;
mảng = { 1, 2, 3 }; // mảng là [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // truyền toàn bộ mảng cho hàm
// mảng bây giờ là [1, 3, 2]
mảng = {2, 3, 1}; // mảng là [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // truyền toàn bộ mảng cho hàm
// mảng bây giờ là [3, 1, 2]
next_permutation(mảng.bắt đầu() + 1, mảng.bắt đầu() + 3); // có thể áp dụng một hàm cho một phần của mảng, nhưng trong thực tế điều này hiếm khi cần thiết
// mảng bây giờ là [3, 2, 1]
Trong trường hợp này, hàm có giá trị trả về kiểu boolean là true nếu hoán vị tiếp theo được tạo và sai nếu không có hoán vị tiếp theo (trường hợp khi hoán vị tối đa theo thứ tự từ điển được truyền cho hàm).
Điều này cho phép sử dụng hàm trong một vòng lặp, điều này sẽ cho phép chúng ta lặp lại tất cả các hoán vị cùng một lúc. Do lập chỉ mục 0, trong thực tế, việc hoán vị các số từ 0 đến n - 1 thường thuận tiện hơn, mặc dù hoán vị chính thức chứa các số từ 1 đến n. Nhưng may mắn thay, điều này không dẫn đến các lớp phủ bổ sung trong mã, bởi vì hàm next_permutation được điều chỉnh theo các hoán vị có chỉ số 0 (và thậm chí cả các phần tử trùng lặp trong một mảng, nhưng bạn có thể tự mình tìm hiểu thêm).
Nói chung, mã để lặp qua tất cả các hoán vị trông giống như sau:
intn; // kích thước hoán vị
vectorperm(n); // perm là viết tắt của "hoán vị", tức là "hoán vị"
for (int i = 0; i < n; i++)
perm[i] = i; // khởi tạo hoán vị ban đầu 0, 1, ..., n - 1
LÀM {
// bên trong vòng lặp, chúng tôi xử lý hoán vị hiện tại
} while (next_permutation(perm.begin(), perm.end())); // nếu không có hoán vị tiếp theo thì kết thúc vòng lặp
Mã này chạy trong O(n! * f(n)), trong đó f(n) là thời gian bạn cần để xử lý một hoán vị cụ thể.
|