Hoán vị mà mỗi phần tử chỉ số phần tử trước hoặc sau nó

Trong phần này chúng ta sẽ xem một bài toán. Ở đây n phần tử được cho trong một mảng. Chúng ta phải kiểm tra xem có tồn tại một hoán vị của mả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ử mảng là {2, 1, 3, 3}. Hoán vị thích hợp giống như {3, 1, 2, 3}. Ở đây 3 đầu tiên chỉ ra có ba phần tử sau nó, 1 chỉ ra chỉ có một phần tử trước nó. 2 chỉ ra có hai phần tử trước nó và 3 cuối cùng chỉ ra 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";
  }
}

Kết quả

Permutation is present