Một hoán vị trong đó mỗi phần tử cho biết số phần tử trước hoặc sau nó?

Trong phần này chúng ta sẽ thấy một vấn đề. Ở đây n phần tử được cho trong một mảng. Chúng ta phải kiểm tra xem có một hoán vị của mảng đó tồn tại hay không, sao cho mỗi phần tử chỉ ra số lượng phần tử có mặt trước hoặc sau nó.

Giả sử các phần tử của mảng là {2, 1, 3, 3}. Hoán vị thích hợp giống như {3, 1, 2, 3}. Ở đây, số 3 đầu tiên cho biết có ba phần tử bên cạnh nó, số 1 cho biết chỉ có một phần tử trước đó. Số 2 cho biết có hai phần tử trước nó và 3 phần cuối cho biết có ba phần tử trước nó.

Thuật toán

checkPermutation (arr, n)

begin
   define a hashmap to hold frequencies. The key and value are of integer type of the map.
   for each element e in arr, do
      increase map[e] by 1
   done
   for i := 0 to n-1, do
      if map[i] is non-zero, then
         decrease map[i] by 1
      else if map[n-i-1] is non-zero, then
         decrease map[n-i-1] by 1
      else
         return false
      end if
   done
   return true
end

Ví dụ

#include<iostream>
#include<map>
using namespace std;
bool checkPermutation(int arr[], int n) {
   map<int, int> freq_map;
   for(int i = 0; i < n; i++){ //get the frequency of each number
      freq_map[arr[i]]++;
   }
   for(int i = 0; i < n; i++){
      if(freq_map[i]){ //count number of elements before current element
         freq_map[i]--;
      } else if(freq_map[n-i-1]){ //count number of elements after current element
         freq_map[n-i-1]--;
      } else {
         return false;
      }
   }
   return true;
}
main() {
   int data[] = {3, 2, 3, 1};
   int n = sizeof(data)/sizeof(data[0]);
   if(checkPermutation(data, n)){
      cout << "Permutation is present";
   } else {
      cout << "Permutation is not present";
   }
}

Đầu ra

Permutation is present