std::is_permutation

#include <algorithm>

// So sánh bằng toán tử ==
template <class ForwardIterator1, class ForwardIterator2>
bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1,
                     ForwardIterator2 first2);

// Sử dụng hàm vị từ so sánh
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
bool is_permutation (ForwardIterator1 first1, ForwardIterator1 last1,
                     ForwardIterator2 first2, BinaryPredicate pred);

Kiểm tra xem hai phạm vi (range) có phải là hoán vị của nhau hay không. Nghĩa là, hai phạm vi chứa cùng các phần tử, nhưng có thể theo thứ tự khác nhau.

Tham số

first1

• Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi thứ nhất.

last1

• Forward Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi thứ nhất. Phạm vi thứ nhất là [first1, last1).

first2

• Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi thứ hai.

pred

• Một hàm vị từ (binary predicate) nhận hai đối số (một phần tử từ phạm vi thứ nhất và một phần tử từ phạm vi thứ hai) và trả về true nếu hai phần tử được coi là khớp, false nếu không. (Phiên bản 2)

Giá trị trả về

true

• Nếu phạm vi thứ hai là hoán vị của phạm vi thứ nhất, nghĩa là:
  • Hai phạm vi chứa cùng số lượng phần tử.
  • Mỗi phần tử trong phạm vi thứ nhất xuất hiện trong phạm vi thứ hai với cùng số lần xuất hiện, nhưng có thể theo thứ tự khác.

false

• Nếu phạm vi thứ hai không phải là hoán vị của phạm vi thứ nhất.

Đặc điểm

1. Phạm vi thứ hai (first2 đến hết) phải chứa ít nhất số phần tử bằng phạm vi thứ nhất. Nếu không, kết quả có thể không như mong đợi.
2. Phạm vi [first1, last1) là "nửa mở", không bao gồm phần tử last1.
3. Phiên bản 1 của is_permutation() sử dụng toán tử == để so sánh các phần tử. Phiên bản 2 cho phép bạn tùy chỉnh cách so sánh bằng hàm vị từ.
4. is_permutation() không quan tâm đến thứ tự của các phần tử, chỉ quan tâm đến sự xuất hiện và số lần xuất hiện của chúng.
5. is_permutation() thường được sử dụng để:
   • Kiểm tra xem hai tập hợp có chứa cùng các phần tử hay không, bất kể thứ tự.
   • Xác minh xem một chuỗi có phải là đảo chữ (anagram) của một chuỗi khác hay không.
   • Kiểm tra xem hai dãy có tương đương nhau về mặt nội dung, nhưng có thể được sắp xếp khác nhau hay không.
6. Độ phức tạp của is_permutation() là O(n²) trong trường hợp xấu nhất. Nếu bạn làm việc với các tập hợp lớn, hãy cân nhắc sử dụng các cấu trúc dữ liệu hoặc thuật toán hiệu quả hơn (ví dụ: std::unordered_map để đếm số lần xuất hiện).

Ví dụ

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

// Hàm vị từ so sánh hai ký tự (không phân biệt hoa thường)
bool caseInsensitiveCompare(char a, char b) {
  return std::tolower(a) == std::tolower(b);
}

int main() {
  std::vector<int> numbers1 = {1, 2, 3, 4, 5};
  std::vector<int> numbers2 = {5, 4, 3, 2, 1};
  std::vector<int> numbers3 = {1, 2, 3, 4, 6};
  std::vector<int> numbers4 = {1, 1, 2, 2, 3};
  std::vector<int> numbers5 = {3, 2, 2, 1, 1};

  // Phiên bản 1: Kiểm tra hoán vị giữa numbers1 và numbers2
  if (std::is_permutation(numbers1.begin(), numbers1.end(), numbers2.begin())) {
    std::cout << "numbers1 and numbers2 are permutations of each other.\n";
  } else {
    std::cout << "numbers1 and numbers2 are not permutations of each other.\n";
  }

  // Phiên bản 1: Kiểm tra hoán vị giữa numbers1 và numbers3
  if (std::is_permutation(numbers1.begin(), numbers1.end(), numbers3.begin())) {
    std::cout << "numbers1 and numbers3 are permutations of each other.\n";
  } else {
    std::cout << "numbers1 and numbers3 are not permutations of each other.\n";
  }

  // Phiên bản 1: Kiểm tra hoán vị giữa numbers4 và numbers5
  if (std::is_permutation(numbers4.begin(), numbers4.end(), numbers5.begin())) {
      std::cout << "numbers4 and numbers5 are permutations of each other.\n";
  } else {
      std::cout << "numbers4 and numbers5 are not permutations of each other.\n";
  }

  std::string str1 = "listen";
  std::string str2 = "silent";
  std::string str3 = "hello";

  // Phiên bản 2: Kiểm tra đảo chữ giữa str1 và str2 (không phân biệt hoa thường)
  if (std::is_permutation(str1.begin(), str1.end(), str2.begin(), caseInsensitiveCompare)) {
    std::cout << "str1 and str2 are anagrams (case-insensitive).\n";
  } else {
    std::cout << "str1 and str2 are not anagrams (case-insensitive).\n";
  }

    // Phiên bản 1: Kiểm tra hoán vị giữa str1 và str2
    if (std::is_permutation(str1.begin(), str1.end(), str2.begin())){
        std::cout << "str1 and str2 are anagrams.\n";
    } else {
        std::cout << "str1 and str2 are not anagrams.\n";
    }

  // Phiên bản 1: Kiểm tra hoán vị giữa str1 và str3
  if (std::is_permutation(str1.begin(), str1.end(), str3.begin())) {
      std::cout << "str1 and str3 are anagrams.\n";
  } else {
      std::cout << "str1 and str3 are not anagrams.\n";
  }

  return 0;
}