std::next_permutation

#include <algorithm>

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

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

Sắp xếp lại (hoán vị) các phần tử trong một phạm vi (range) thành hoán vị kế tiếp theo thứ tự từ điển tăng dần. Nếu không tồn tại hoán vị kế tiếp lớn hơn, nó sẽ sắp xếp lại phạm vi thành hoán vị nhỏ nhất (tức là sắp xếp tăng dần).

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.

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 đã được tạo thành công.

false

• Nếu phạm vi đã ở hoán vị lớn nhất (tức là được sắp xếp giảm dần) và đã được sắp xếp lại thành hoán vị nhỏ nhất (tức là sắp xếp tăng 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. next_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. next_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. next_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. next_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ử.
   • 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ị.
   • Thử nghiệm các trường hợp khác nhau của một bài toán bằng cách duyệt qua các hoán vị.

Phân biệt với prev_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 = {1, 2, 3};

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

  std::string str = "bca";
  std::cout << "\nNext lexicographically greater permutation of bca: ";
  if (std::next_permutation(str.begin(), str.end()))
      std::cout << str << std::endl;
  else
      std::cout << str << " is already the largest permutation" << std::endl;

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

  return 0;
}

Các hàm liên quan

prev_permutation	Biến đổi một phạm vi thành hoán vị kế tiếp nhỏ hơn theo thứ tự từ điển
lexicographical_compare	So sánh hai phạm vi theo thứ tự từ điển