std::prev_permutation

#include <algorithm>

// So sánh bằng toán tử <
template <class BidirectionalIterator>
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last);

// Sử dụng hàm so sánh tùy chỉnh
template <class BidirectionalIterator, class Compare>
bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last,
                       Compare comp);

Biến đổi một phạm vi (range) thành hoán vị kế tiếp nhỏ hơn theo thứ tự từ điển (lexicographical order). Nếu không tồn tại hoán vị kế tiếp nhỏ hơn, nó sẽ sắp xếp lại phạm vi thành hoán vị lớn nhất (tức là sắp xếp giảm dần) và trả về false.

Tham số

first

• Bidirectional Iterator trỏ đến phần tử đầu tiên trong phạm vi cần tìm hoán vị kế tiếp nhỏ hơn.

last

• Bidirectional Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi. Phạm vi là [first, last).

comp

• Một hàm hoặc đối tượng hàm (comparator) nhận hai đối số (hai phần tử trong phạm vi) và trả về true nếu phần tử thứ nhất được coi là nhỏ hơn phần tử thứ hai theo tiêu chí so sánh, false nếu ngược lại. (Phiên bản 2)

Giá trị trả về

true

• Nếu hoán vị kế tiếp nhỏ hơn được tạo ra thành công.

false

• Nếu phạm vi đã ở hoán vị nhỏ nhất (tức là được sắp xếp tăng dần) và không thể tạo ra hoán vị kế tiếp nhỏ hơn. Trong trường hợp này, phạm vi sẽ được sắp xếp lại thành hoán vị lớn nhất (tức là sắp xếp giảm dần).

Đặc điểm

1. Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
2. prev_permutation() thay đổi trực tiếp thứ tự các phần tử trong phạm vi gốc, không tạo ra một phạm vi mới.
3. prev_permutation() yêu cầu Bidirectional Iterator, cho phép di chuyển theo cả hai hướng (tiến và lùi).
4. Trong C++11 trở lên, bạn có thể sử dụng biểu thức lambda cho hàm so sánh comp (phiên bản 2) để code ngắn gọn và dễ đọc hơn.
5. prev_permutation() thay đổi trực tiếp thứ tự các phần tử trong phạm vi đầu vào, không tạo ra một phạm vi mới.
6. prev_permutation() thường được sử dụng để:
   • Duyệt qua tất cả các hoán vị có thể có của một tập hợp các phần tử theo thứ tự từ điển giảm dần.
   • Giải các bài toán yêu cầu tìm kiếm hoặc liệt kê các hoán vị theo chiều ngược.

Phân biệt với next_permutation()

• next_permutation() tìm hoán vị kế tiếp lớn hơn theo thứ tự từ điển.
• prev_permutation() tìm hoán vị kế tiếp nhỏ hơn theo thứ tự từ điển.

Ví dụ

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int main() {
  std::vector<int> numbers = {3, 2, 1};

  std::cout << "All permutations of {3, 2, 1} in reverse order:\n";
  do {
    for (int x : numbers) {
      std::cout << x << " ";
    }
    std::cout << std::endl;
  } while (std::prev_permutation(numbers.begin(), numbers.end()));

  std::string str = "cba";
  std::cout << "\nPrevious lexicographically smaller permutation of cba: ";
  if (std::prev_permutation(str.begin(), str.end()))
      std::cout << str << std::endl;
  else
      std::cout << str << " is already the smallest permutation" << std::endl;
    
  std::vector<int> numbers2 = {1, 2, 3};
  std::cout << "\nPrevious lexicographically smaller permutation of {1, 2, 3}: ";
  if (std::prev_permutation(numbers2.begin(), numbers2.end())) {
      for (int x : numbers2)
          std::cout << x << " ";
      std::cout << std::endl;
  } else {
      std::cout << "{1, 2, 3} is already the smallest permutation" << std::endl;
      std::cout << "Rearranging to the largest permutation: ";
      for (int x : numbers2)
          std::cout << x << " ";
      std::cout << std::endl;
  }

  return 0;
}

Các hàm liên quan

next_permutation	Sắp xếp lại các phần tử trong một phạm vi thành hoán vị kế tiếp theo thứ tự từ điển tăng dần
lexicographical_compare	So sánh hai phạm vi theo thứ tự từ điển